Родился 7 февраля 1909 года в Киеве (Украина). Окончил 7 классов. Работал стеклодувом на Киевском стекольном заводе "Червона Гута". С 1 июня 1932 года в рядах Красной Армии (призван по партийной мобилизации). В 1933 году окончил Качинскую военную авиационную школу лётчиков. Служил в ВВС Белорусского военного округа: пилот штурмовой эскадрильи в 252-й АБР, с июля 1935 года - инструктор-лётчик в 40-й АБР, с августа 1938 года - командир звена в 15-м ИАП (70-я АБР).

Участник похода советских войск в Западную Белоруссию в сентябре 1939 года и Советско-Финляндской войны 1939-1940 гг. в составе 15-го ИАП и 72-го САП, летал на И-15бис, воздушных побед не имел. С 31 марта 1940 года - командир звена 72-го САП ВВС Северного флота, с июня 1941 года - заместитель командира 1-й эскадрильи.

С 22 июня 1941 года старший лейтенант А. А. Коваленко в действующей армии: в составе 72-го САП СФ, летал на И-16. Участник обороны Мурманска и боевых действий в Заполярье. 29 июня 1941 года был ранен при бомбардировке аэродрома, до августа лечился. С октября 1941 года - командир эскадрильи в 78-м ИАП СФ, летал на "Харрикейне". В марте 1942 года был переведён в 2-й Гвардейский ИАП СФ. Летал на "Харрикейне", "Киттихауке" и "Аэрокобре".

К маю 1942 года командир 2-й эскадрильи 2-го Гвардейского истребительного авиационного полка (ВВС Северного флота) Гвардии капитан А. А. Коваленко совершил 146 боевых вылетов, в 22 воздушных боях сбил лично 11 и в группе 6 самолётов противника (в наградном листе говорится о 11 личных и 7 групповых победах). Указом Президиума Верховного Совета СССР от 14 июня 1942 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 866).

В январе 1943 года Гвардии майор А. А. Коваленко был отстранён от боевой работы по состоянию здоровья. К тому времени выполнил 207 боевых вылетов, провёл 38 воздушных боёв, в которых сбил лично 13 и в составе группы 6 самолётов противника.

В феврале 1943 года был направлен на Высшие курсы офицерского состава ВВС ВМФ. После их окончания, с января 1944 года - помощник командира 3-го учебного авиационного полка по лётной подготовке и воздушному бою ВВС Северного флота.

После окончания войны продолжал служить в ВВС. С 1945 года Гвардии подполковник А. А. Коваленко - в запасе по инвалидности. Жил в Москве. Умер 21 июня 1984 года, похоронен на Кунцевском кладбище. Бюст А. А. Коваленко в числе 53-х лётчиков-североморцев, удостоенных звания Героя Советского Союза, установлен в посёлке Сафоново (ЗАТО город Североморск Мурманской области).

Награждён орденами: Ленина (14.06.1942), Красного Знамени (08.09.1941, 13.02.1942), Отечественной войны 1-й степени; медалями, в том числе "За боевые заслуги" (03.11.1944); Крестом "За лётные заслуги" (Великобритания, 18.03.1942).

Список известных воздушных побед А. А. Коваленко:

Д а т а	Противник	Место падения самолёта или проведения воздушного боя	Свой самолёт
15.08.1941	1  Ме-110	Мурманск - Горячево	И-16
26.08.1941	3  Ю-88  (в группе 3/9)	Ваенга - Луостари
27.08.1941	1  Ме-109	озеро Нял-Явр
02.09.1941	1  Ме-109  (в группе 1/6)	Мурманск
03.09.1941	1  Ме-109	река Западная Лица - река Лебяжка
09.09.1941	1  Ю-87	западнее озеро Ура-Губское
10.09.1941	1  Ме-109	озеро Куырк-Явр
12.09.1941	1  Ю-88  (в паре)	колхоз Большая Западная Лица
15.09.1941	1  Ме-110	Западная Лица
	1  Ю-87	озеро Куырк-Явр
06.10.1941	1  Ю-88  (в группе 1/8)	Ура-Губа
24.03.1942	1  Ме-109	озеро Куосме-Ярви	"Харрикейн"
04.04.1942	1  Ме-109	южнее озеро Ленк-Явр
12.04.1942	1  Ме-110	озеро Чапр
15.04.1942	1  Ю-87	Мурманск
29.06.1942	1  Ме-109		"Киттихаук"
26.12.1942	1  Ю-87	юго-западнее Минкино	"Аэрокобра"
Всего сбитых самолётов - 13 + 6;  боевых вылетов - 207;  воздушных боёв - 38.

Из фотоматериалов разных лет:

Из материалов прессы военных лет: