Родился 22 ноября 1914 года в селе Царицын Кут Запорожской области. Закончил один курс Института Механизации и электрификации сельского хозяйства. В ВМФ с 1934 года. В 1936 году окончил школу военных пилотов. Участник советско-финляндской войны 1939-1940 годов.

В годы Великой Отечественной войны был командиром эскадрильи 40-го авиационного полка 13-й авиационной дивизии пикирующих бомбардировщиков ВВС Черноморского флота. К октябрю 1944 года капитан А. А. Гнедой совершил 140 боевых вылетов, потопил миноносец, подводную лодку, транспортное судно, тральщик, 6 барж, взорвал железнодорожный мост, уничтожил 15 самолетов противника.

Звание Героя Советского Союза присвоено А. А. Гнедому 6 марта 1945 года.

После войны продолжал службу в ВМФ. В 1951 году закончил командный факультет Военно-морской академии им. К. Е. Ворошилова, с 1953 года занимался преподавательской работой.

С 1960 года полковника. А. Гнедой находился в запасе. Работал старшим инженером Всесоюзного проектно-конструкторского института технологии электротехнического производства.

Награжден орденом Ленина, двумя орденами Красного Знамени, орденами Александра Невского, Отечественной войны I степени, Красной Звезды, медалями.

Герои Петроградской стороны : краткие биографии Героев Советского Союза, Героев Социалистического Труда и почетных граждан Санкт-Петербурга, чья жизнь была связана с Петроградской стороной / составители: В. И. Щербаков, Г. М. Атаманова, И. В. Вчерашняя ; редактор: О. Капполь. - Санкт-Петербург : Златоуст, 2010.