Родился 16 октября 1914 г. в поселке Нижние Серги Пермской губернии. Окончил 10 классов, в 1935 г. — Свердловский строительный техникум. Работал на металлургическом заводе. В 1938 г. Фетодов по первому разряду был выпущен Оренбургской военной школой летчиков.
В 1939-1940 гг. ст. лейтенант Федотов выполнил несколько десятков боевых вылетов в ходе советско-финляндской войны.
С июня 1941 г. — на фронте. Комэск, штурман, а позднее и командир 63-го гиап (169 иап) воевал на Западном, Волховском, Северо-Западном, Калининском, Брянском, 1-м Прибалтийском фронтах. Ему довелось сражаться почти на всех серийных отечественных истребителях своего времени: на И-153, И-16, МиГ-3, Як-1, Ла-5. Уже первой военной осенью за несколько сбитых вражеских самолетов Федотов был награжден орденом Ленина.
С особенной силой его воинское дарование раскрылось после перевооружения полка на Ла-5, который командир полка освоил одним из первых в декабре 1942 г. 16 декабря он сбил "новый" ФВ-190 на "новом" же Ла-5. А под Новый год, 29 декабря, в нескольких вылетах он сбил сразу 3 самолета противника. Изощренный в воздушном бою мастер высшего воздушного пилотажа, решительный командир, доброжелательный и приветливый человек, он был живым кумиром молодых летчиков. "Андрей Андреевич всегда оставался человеком большой души и редкой доброты", — вспоминал о командире один из его питомцев, легендарный Алексей Маресьев. 15 декабря 1943 г., возвращаясь с боевого задания, где ему удалось сбить Ю-88, гвардии полковник А. Федотов неожиданно был атакован четверкой Ме-109 и погиб.
Он провел более 200 боевых вылетов, сбил лично 22 самолета противника и несколько в группе.
Герой Советского Союза (1.5.43). Награжден 2 орденами Ленина, орденом Красного Знамени, орденом Александра Невского, 2 орденами Отечественной войны 1-й ст.