Родился 18 августа 1917 года в селе Кудашево (Божедаровский район Днепропетровской области Украины). С 12 апреля 1938 года в рядах Красной Армии, призван Щорским РВК (Днепропетровская область Украины). В 1939 году окончил Качинскую военную авиационную школу лётчиков. Служил в строевых частях ВВС.

Участник Советско-Финляндской войны 1939-1940 гг. в составе неустановленной авиачасти. Затем служил в 167-м ИАП (ВВС Среднеазиатского военного округа, базировался на аэродроме близ посёлка Мары).

С апреля 1944 года старший лейтенант А. А. Коваленко на фронтах Великой Отечественной войны в должности заместителя командира эскадрильи 352-го ИАП (273-я ИАД). Летал на "Аэрокобре".

К 9 мая 1945 года командир 3-й эскадрильи 352-го истребительного авиационного полка (273-я истребительная авиационная дивизия, 6-й истребительный авиационный корпус, 16-я Воздушная армия, 1-й Белорусский фронт) капитан А. А. Коваленко совершил 126 боевых вылетов, в 16 воздушных боях сбил лично 5 самолётов противника.

После окончания войны продолжал служить в ВВС (в составе 30-го Гвардейского ИАП). С 1 июня 1953 года Гвардии капитан А. А. Коваленко - в запасе.

Награждён орденами: Красного Знамени (06.08.1944, 16.06.1945, 07.04.1970), Александра Невского (04.02.1945); медалями, в том числе "За боевые заслуги" (20.06.1949).