Родился в дворянской семье в 1800 году в Кинешемском уезде Костромской губернии. Образование получил в Горном кадетском корпусе, из которого в 1818 году поступил подпрапорщиком в лейб-гвардии Преображенский полк.
Участвовал в русско-турецкой войне 1828—1829 годов, в подавлении Польского мятежа в 1831 году За отличие при штурме Варшавы награждён орденом св. Владимира 4-й степени с бантом. В 1832 году получил чин капитана.
В 1835 году Катенин на Калишских манёврах обращает на себя внимание императора Николая I и назначается к нему флигель-адъютантом. Два года спустя Катенин ужеполковник, а в 1839 году назначен комендантом Императорской главной квартиры, но в том же году переведён на Кавказ, где в должности начальника штаба 1-го пехотного корпуса принял участие в военных действиях против горцев и за отличие при Ахульго награждён золотой шпагой с надписью «За храбрость».
В 1842 году Катенин был назначен начальником штаба отдельного гренадерского корпуса, на следующий год уже был генерал-майором.
12 января 1846 года Катенин был награждён орденом св. Георгия 4-й степени (№ 7380 по списку Григоровича—Степанова).
В 1848 году назначен командиром Лейб-гвардии Преображенского полка, через год удостаивается чина генерал-адъютанта, и в 1852 году назначен дежурным генералом при Главном штабе Его Императорского Величества.
В 1853 году Катенина производят в генерал-лейтенанты, а в следующем году на него возложено исполнение обязанностей товарища военного министра с оставлением в должности дежурного генерала.
В 1856 году Катенин был уволен со всех должностей и 7 апреля 1857 года назначен командиром отдельного Оренбургского корпуса и Оренбургским и Самарским генерал-губернатором.
О назначении Александра Андреевича Катенина генерал-губернатором известный военный историк Николай Гаврилович Залесов, служивший в то время офицером Генерального штаба при отдельном Оренбургском корпусе, в своих «Записках» вспоминает:
Назначение Катенина в Оренбургский край совпало с крайним развитием дерзких набегов киргизов на селения и форпосты Оренбургской линии и грабежей караванов. Крутые меры его предшественника, графа Василия Алексеевича Перовского, не смогли обуздать хищников и лишь озлобили их. Катенин тотчас же циркулярно оповестил киргизов, что если они смирятся, то будут прощены. Первым отозвался на призыв главный организатор разбойничьих набегов Исет Кутебаров, который писал «справедливейшему генерал-адъютанту Катенину», что причиной неудовольствия киргизов были суровые меры его предшественника и обещал смириться. Катенин вызвал его к себе «не как к грозному начальнику, а как к доброму отцу, которырый радуется, когда может простить заблудших детей своих», и, ласково приняв Кутебарова, склонил его быть верным слугою государя. Пример Кутебарова повлиял на других, и набеги сильно сократились.
Для полного умиротворения края Катенин объехал его и предпринял ряд мер к развитию промышленности и распространению грамотности. Им было организовано в 1858 году пароходство по реке Белая, вошедшее в связь с пароходствами по рекам Волга и Кама, в том же году был учреждён почтовый тракт между Орской крепостью и фортом Перовский. Только на одних форпостах им было устроено до 80 школ, не считая городских училищ для детей обоего пола в городах и крупных станицах.
Изменена была и политика по отношению к среднеазиатским ханствам. В октябре 1857 года Катенин представил свои соображения по этому предмету министрам военному и иностранных дел. Предложения Оренбургского генерал-губернатора совпали с намерениями правительства, и Александру Катенину было поручено составить письменные инструкции для предполагаемой миссии.
После продолжительной переписки между министерствами и оренбургским генерал-губернатором, вопрос о снаряжении новой миссии в Среднюю Азию в конце концов решился положительно. Начальником её и полномочным представителем русского правительства был назначен полковник Николай Павлович Игнатьев, а секретарём — Егор Борисович Килевейн. Посольство посетило Хиву и Бухару, Николаю Игнатьеву удалось подписать торговые договора с обоими ханами. Несмотря на кажущийся полный успех посольства Игнатьева, сами члены миссии в отношении исполнения бухарцами и хивинцами записанных на бумаге договорённостей были настроены весьма скептически.
Весной 1859 года были снаряжены две научные экспедиции в Среднюю Азию: одна под начальством Алексея Ивановича Бутакова для завершения исследований Аральского моря и устьев реки Аму-Дарья, а вторая экспедиция, под начальством Виктора Дезидерьевича Дандевиля — для описи Мангышлакского берега Каспийского моря.
Возвращаясь из инспекционной поездки по землям Уральского казачьего войска, на подъезде к Оренбургу 24 июня 1860 года Александр Андреевич Катенин умер от воспаления лёгких.
Именем Катенина был назван станичный поселок во втором военном отделе Оренбургского казачьего войска.