﻿Родился 30 марта 1920 года в селе Кесова - Гора Калининской области, в семье рабочего. Окончил среднюю школу. В Красной Армии с 1938 года. Призван Мытищинским РВК Московской области. Окончил военную авиационную школу имени В. П. Чкалова в 1939 году.
Участник Великой Отечественной войны с июня 1941 года. Прошёл путь от рядового лётчика до заместителя командира истребительного авиаполка. Принимал участие в обороне Одессы, Харькова, в наступательных боях под Ростовом, Таганрогом, Мелитополем, на территории Германии.
24 августа 1943 года за воинскую доблесть и мужество, проявленные при обороне Одессы и в Сталинградской битве, в боях под Ростовом, Таганрогом и Мелитополем, 265 боевых вылетов и участие в 65 воздушных боях, в которых сбил 11 самолётов противника лично и 6 - в составе группы, командир эскадрильи 9-го Гвардейского истребительного авиаполка  ( 6-я Гвардейская истребительная авиационная дивизия, 8-я Воздушная армия, Южный фронт )  Гвардии капитан А. В. Алелюхин удостоен звания Героя Советского Союза.
1 ноября 1943 года за умелое руководство пилотами эскадрильи в боях за освобождение Донбасса, 410 боевых вылетов и участие в 114 воздушных боях, в которых лично сбил ещё 26 самолётов противника, награждён второй медалью "Золотая Звезда".
Всего за годы войны совершил 601 боевой вылет, провёл 258 воздушных боёв, уничтожил 40 вражеских самолётов лично и 17 - в группе с товарищами.
После войны продолжал служить в ВВС на командных и штабных должностях. Окончил Военную академию имени М. В. Фрунзе в 1948 году и Военную академию Генерального штаба в 1954 году. С 1958 года генерал - майор авиации А. В. Алелюхин - в запасе. Умер 29 октября 1990 года.
Награждён орденами: Ленина  ( дважды ), Красного Знамени   ( трижды ), Суворова 3-й степени, Александра Невского, Отечественной войны 1-й степени, Трудового Красного Знамени, Красной Звезды  ( дважды ), "За службу Родине в Вооружённых Силах СССР" 3-й степени; медалями.