Родился 20 сентября 1923 года в деревне Мощиново (ныне Монастырщинский район Смоленской области). В 1931-1934 гг. жил в Москве, с 1934 года - в селе Кудиново (Ногинский район Московскойобласти). В 1940 году окончил 9 классов школы в селе Кудиново и Реутовский аэроклуб. После окончания курсов токарей с декабря 1940 года работал токарем по металлу на машиностроительном заводе № 20 в Москве. С февраля 1941 года в рядах Красной Армии. В марте 1943 года окончил Качинскую военную авиационную школу лётчиков. С марта по май 1943 года был лётчиком 8-го ЗИАП ВВС Приволжского военного округа (посёлок Багай-Барановка, Вольский район Саратовской области).

С мая 1943 года сержант А. И. Колдунов на фронтах Великой Отечественной войны в составе 866-го ИАП. Занимал должности старшего лётчика, командира звена, заместителя командира и командира эскадрильи. Летал на Як-1, Як-9 и Як-3. Воевал на Юго-Западном и 3-м Украинском фронтах. Участвовал в Изюм-Барвенковской, Донбасской, Запорожской, Никопольско-Криворожской, Одесской, Ясско-Кишинёвской, Белградской, Будапештской и Венской операциях.

Свою первую победу А. И. Колдунов одержал 18 июля 1943 года, сбив над Северским Донцом вражеский Ю-87. 1 сентября 1943 года его самолёт был подбит на взлёте парой Ме-109, сам он был легко ранен осколком разорвавшегося снаряда в поясницу. Однако, молодой лётчик не растерялся: выключив двигатель, спланировал и аккуратно посадил истребитель рядом с аэродромом. Через 2 дня он вышел из госпиталя и продолжил боевую работу. Уже осенью 1943 года лётчик довёл число своих личных побед до 10, был назначен командиром звена, стал признанным асом в полку и в дивизии.

К 24 мая 1944 года командир эскадрильи 866-го истребительного авиационного полка (288-я истребительная авиационная дивизия, 17-я Воздушная армия, 3-й Украинский фронт) капитан А. И. Колдунов совершил 223 боевых вылета, в 45 воздушных боях сбил лично 15 и в составе пары 1 самолёт противника. Указом Президиума Верховного Совета СССР от 2 августа 1944 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 3464).

Осенью 1944 года А. И. Колдунову был передан именной Як-3 с надписью: "От колхозника Богаченко Г.А.". На этой машине он воевал до последнего дня, позднее она была передана Румынскому правительству и находилась в Бухарестском доме пионеров.

Зимой 1944-1945 гг. А. И. Колдунов продолжил список побед в боях над Венгрией, за 3 месяца сбив 15 неприятельских самолётов. В феврале 1945 года он возглавил "группу по расчистке воздуха", куда входили Герои Советского Союза капитаны Р. И. Сидоренко и Н. Г. Сурнев, а также старший лейтенант М. И. Шишов и лейтенант С. Г. Шамонов. До конца войны эти лётчики сбили 32 самолёта противника, не имея своих потерь. Свои последние победы советский ас одержал западнее Вены, 11 апреля 1945 года.

К 9 мая 1945 года командир эскадрильи 866-го истребительного авиационного полка (288-я истребительная авиационная дивизия, 17-я Воздушная армия, 3-й Украинский фронт) майор А. И. Колдунов совершил 412 боевых вылетов, в 96 воздушных боях сбил лично 46 и в составе пары 1 самолёт противника. 23 февраля 1948 года Указом Президиума Верховного Совета СССР был награждён второй медалью "Золотая Звезда".

После войны продолжал служить в ВВС. До марта 1946 года продолжал командовать эскадрильей 866-го ИАП (в Южной группе войск, Болгария), летал на Як-3. В 1952 году окончил Военно-Воздушную академию (в Монино). В июле 1952 - апреле 1955 гг. был командиром 394-го ИАП (в Северо-Кавказском военном округе и Северо-Кавказской армии ПВО; город Грозный), в апреле 1955 - сентябре 1958 гг. - командир 86-й ИАД ПВО (в Куйбышевском корпусе ПВО). Летал на МиГ-15бис и МиГ-17.

В 1960 году окончил Военную академию Генерального штаба. С июля 1960 года - заместитель командующего, а в январе 1962 - августе 1965 гг. - командующий авиацией Бакинского округа ПВО. До 1965 года летал на реактивных самолётах. В августе 1965 - июле 1968 гг. - 1-й заместитель командующего войсками Бакинского округа ПВО (штаб - в городе Баку, Азербайджан), в июле 1968 - ноябре 1970 гг. - командующий 11-й отдельной армией ПВО (город Хабаровск). В ноябре 1970 - декабре 1975 гг. - командующий войсками Московского округа ПВО.

С декабря 1975 года - 1-й заместитель главнокомандующего, в июле 1978 - июне 1987 гг. - главнокомандующий Войсками ПВО страны и заместитель министра обороны СССР. В 1978-1987 гг. одновременно командующий войсками ПВО и заместитель главнокомандующего Объединёнными вооружёнными силами государств - участников Варшавского договора. Главный маршал авиации (31.10.1984). Был снят с должности М. С. Горбачёвым после скандального полёта М. Руста на самолёте "Цессна" и его посадки на Красной площади в Москве 28 мая 1987 года. C августа 1987 года - генеральный инспектор Группы генеральных инспекторов Министерства обороны СССР. С мая 1992 года Главный маршал авиации А. И. Колдунов - в отставке.Жил в Москве. Умер 7 июня 1992 года, похоронен на Новодевичьем кладбище (участок 11).

Бронзовый бюст А. И. Колдунова был установлен в деревне Мощиново (открыт 7 октября 1950 года), в 1970-х годах перенесён в город Монастырщина (Смоленская область). В Хабаровске на доме, в котором он жил, установлена мемориальная доска. Его именем названы улица в городе Балашихе (Московская область), а также школа № 30 в городе Электроугли (Московская область) и школа в посёлке Монастырщина (Смоленская область).

Награждён орденами: Ленина (02.08.1944, 18.02.1981, 19.02.1986), Красного Знамени (08.09.1943, 30.01.1944, 29.04.1944, 29.04.1957, 22.02.1968, 19.09.1973), Александра Невского (20.09.1944), Отечественной войны 1-й степени (06.03.1945, 11.03.1985), Красной Звезды (30.12.1956), "За службу Родине в Вооружённых Силах СССР" 3-й степени (30.04.1975); медалями, многими иностранными наградами.