Родился  30.3.1920 года в с. Кесова Гора Кашинского уезда (ныне посёлок городского типа Кесовогорского района Тверской области). В начале 1930-х годов семья переехала в Подмосковье. Работал на Московской фабрике канцелярских товаров. Без отрыва от производства окончил планерную школу при аэроклубе Октябрьского района г. Москвы. В Красной Армии с 1938 года. Через год окончил Борисоглебскую Краснознаменную военную авиационную школу имени В.П. Чкалова. Службу начал в Ленинградском военном округе, в октябре 1940 года переведён в Одессу - в 69-й истребительный авиационный полк, впоследствии - 9-й Гвардейский, с которым прошёл войну до Берлина. В боях в Великую Отечественную войну с 22 июня 1941 года в Одесском военном округе. В составе полка отличился в боях за оборону Одессы, сражался с немецкими асами во время Сталинградской стратегической оборонительной операции с 17 июля по 18 ноября 1942 года на дальних и ближних подступах к городу. Летчики 69-го истребительного авиаполка во взаимодействии с 16-й, 20-й и 17-й воздушными армиями участвовали в Котельниковской операции (12 - 29.12.1942). В боях под Калачом сбил четыре вражеских бомбардировщика, а под Котельниковом и Зимовниками - два "юнкерса" и один "мессершмитт". За эти победы был награждён орденами Ленина и Красного Знамени. Участвовал в освобождении Донбаса,  Южной Украины, Крыма. Войну гвардии капитан А.В. Алелюхин завершил в Берлине в должности командира эскадрильи 9-го гвардейского истребительного авиаполка 6-й гвардейской истребительной авиадивизии 8-й воздушной армии Южного фронта.

За время войны совершил 601 боевой вылет, проведя 258 воздушных боёв, лично уничтожил 40 вражеских самолётов и ещё 17 - в составе группы. К концу войны воевал на именном истребителе Ла-7 с надписью на борту «Алексею Алелюхину от коллектива треста № 41 НКАП». Последний воздушный бой провёл в небе Германии, сбив Fw-190 противника.

После войны - лётчик-испытатель. Работал на командных должностях. В 1948 году окончил Военную академию имени М.В. Фрунзе, в 1954 году - Высшую военную академию имени К.Е. Ворошилова (Военная академия Генштаба). В 1950 году гвардии полковник А.В. Алелюхин назначен командиром вновь сформированной 28-й истребительной авиационной дивизии. С ноября 1950 по февраль 1951 года во главе соединения участвовал в боевых действиях Корейской войны, боевых вылетов не выполнял. С 1985 года генерал-майор авиации (1971) А.В. Алелюхин - в отставке. Жил в Москве, где умер 29 октября 1990 года. Похоронен на Новодевичьем кладбище.

Дважды Герой Советского Союза (24.8.1943; 1.11.1943).

Награждён: двумя орденами Ленина (10.02.1942; 24.08.1943), тремя орденами Красного Знамени (05.11.1941, 01.08.1943, 20.04.1945), орденами Суворова 3-й степени (08.10.1943), Александра Невского (14.07.1943), Отечественной войны 1-й степени (11.03.1985), Трудового Красного Знамени (1968), двумя орденами Красной Звезды (22.09.1942, 1950), орденом "За службу Родине в ВС СССР" 3-й степени (1975), медалями.

Библиография

Дважды Герои Советского Союза. - Москва : Воениздат, 1973.

Долгов И.А. Золотые звезды калининцев. - Москва, 1983. -  Кн. 1. - С. 30-34 : ил.

Герои Советского Союза : крат. биогр. слов. - Москва, 1987. - Т.1. - С. 45.
 
Гордость земли Тверской : [сборник / науч. ред. В.И. Лавренов]. - Тверь, 2014. - С. 52-53 : ил.

Воробьёв В.М. Обаяние силы и уверенности // Герои Советского Союза на Тверской земле : биогр. очерки : в 5 т. / науч. ред. Г.С. Горевой. - Тверь, 2015. - Т. 1. - С.11-16 : ил.