Родился 20 апреля 1922 года в деревне Варваровка (ныне Медынский район Калужской области). С 1930 жил в городе Коломна (Московская область). В 1939 году окончил 8 классов средней школы № 22, в 1940 году - городской аэроклуб имени Водопьянова (его инструктором был старший брат - Иван Елдышев). С 27 марта 1940 года в рядах Красной Армии, призван Коломенским РВК (Московская область). В ноябре 1940 года окончил Качинскую военную авиационную школу лётчиков. С января 1941 года служил в должности пилота 16-го ИАП (ВВС Московского военного округа).

С 22 июня 1941 года сержант А. А. Елдышев на фронтах Великой Отечественной войны в составе 16-го ИАП (6 ИАК ПВО, Московская зона ПВО), летал на МиГ-3. 27 сентября 1941 года направлен в 565-й ИАП (6 ИАК ПВО, Московская зона ПВО), летать тоже на МиГ-3. С января 1942 года старшина А. А. Елдышев служил в 487-м ИАП (101-я ИАД ПВО, Воронежско-Борисоглебский район ПВО), продолжая летать на МиГ-3. 21 сентября 1942 года младший лейтенант А. А. Елдышев был направлен для продолжения службы в 910-й ИАП ОН ПВО (9 октября 1943 года преобразован в 148-й Гвардейский ИАП ОН), где летал уже на "Яках" (Як-1, Як-7 и Як-9).

К 23 мая 1943 года лётчик 910-го истребительного авиационного полка Особого назначения ПВО (101-я истребительная авиационная дивизия, Войска ПВО страны) лейтенант А. А. Елдышев совершил 272 боевых вылета, в 17 воздушных боях сбил лично 10 в составе группы 2 самолёта противника (По данным наградного листа, на 19 мая 1943 года имел 11 личных и 7 групповых побед, но эта информация не подтверждается какими-либо оперативными и отчётными документами). Указом Президиума Верховного Совета СССР от 9 октября 1943 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда".

17 декабря 1943 года старший лейтенант А. А. Елдышев погиб при выполнении очередного задания под Киевом (согласно некоторым источникам, сбит в воздушном бою, воспользовался парашютом и приземлился на вражеской территории; не желая попасть в плен, окружившим его немецким солдатам, застрелился). К тому времени выполнил около 300 боевых вылетов, провёл около 20 воздушных боёв, сбил 11 самолётов противника лично и 2 в группе с другими лётчиками. Похоронен в селе Ивановка (Белоцерковский район Киевской области). Бюст Героя установлен в Коломне, мемориальная доска - на здании Коломенского аэроклуба. Его именем названа улица в Тарусе.

Награждён орденами: Ленина (09.10.1943), Красного Знамени (14.02.1943); медалями.