Школьные годы Александра Гервасьевича совпали с событиями первой русской революции, отзвуки которой докатились и до уездного городка Черкассы на Днепре, где родился будущий писатель. О детстве и юности он рассказывал в своём романе «Первая министерская» (1934).

В годы Первой мировой войны Лебеденко, тогда студент факультета восточных языков Санкт-Петербургского университета, ушёл на фронт в качестве вольноопределяющегося и служил в артиллерийском дивизионе. В 1918 году вступил в ряды Красной Армии, был участником борьбы против генерала Н. Юденича, дважды подвергался аресту по делу «бывших офицеров»: 20 октября 1918 года (освобожден 27 октября 1918 г.) и 14 января 1935 года (был приговорён к высылке в Казахстан на 3 года).

Литературную деятельность Александр Гервасьевич начал во фронтовой газете «Боевая правда». С 1920 по 1925 год работал секретарём редакции газеты «Ленинградская правда». Человек широкого кругозора, влюблённый в своё дело, он много путешествовал. В период между 1923 и 1925 годом побывал в Турции, Китае, Маньчжурии, Монголии, Норвегии, Швеции, Финляндии, Германии, Испании. В 1926–1931 гг., трудился в издании «Красная газета», информационных агентствах РОСТА, ТАСС, издательстве «Молодая гвардия». В 1926 году Лебеденко принимал участие в перелёте Р. Амундсена, Л. Элсуорта и У. Нобиле на дирижабле «Норвегия» по маршруту Европа–Шпицберген–Аляска.

Впечатления от путешествий нашли своё отражение в очерках «Перелёт Москва–Монголия–Пекин» (1925), «Как я летал в Китай» (1926), «На полюс по воздуху» (1927) и многих других.

Умело сочетая увлекательную форму изложения и насыщенность подлинно научным материалом, Лебеденко писал книги и для детей. Например, «Индия, Индия, Индия!!!» (1930), «Крестовый поход» (1930), «Четвёртая пуля Ли Сина» (1931), «Пожар в Испании» (1931) . Важной вехой на творческом пути писателя стала повесть «Восстание на „Святой Анне”» (1930), ставшая предтечей к таким серьёзным романам как «Тяжёлый дивизион» (1932), посвящённом Первой мировой войне, и «Лицом к лицу» (1957), в котором действие разворачивается в Петрограде 1918–1919 гг. Александр Гервасьевич изобразил жизнь революционного города с будничной стороны, описав обыски, офицерские заговоры, суровый быт людей революции.

В 1956 году вернулся в Ленинград, был членом правления Ленинградского отделения Союза писателей СССР, работал в редакции журнала «Звезда». Похоронен на Богословском кладбище Санкт-Петербурга.