Родился 6 мая 1919 года в селе Новоданиловка ныне Акимовского района Запорожской области (Украина) в семье крестьянина.  Окончил 7 классов школы и школу ФЗУ. С августа 1936 года работал слесарем в Мелитопольском паровозном депо, одновременно учился в аэроклубе. В РККА с 1938 года. В сентябре 1939 года окончил 1-ю Качинскую Краснознамённую военную авиационную школу пилотов имени А.Ф.Мясникова. В звании младшего лейтенанта был направлен служить в Ленинградский военный округ.

Участник советско-финляндской войны 1939-1940 годов.

Участник Великой Отечественной войны с июня 1941 года. Воевал в районах Малой Вишеры, Чудова, Новгорода. Совершил 2 боевых вылета на штурмовку войск противника.

2 ноября 1941 года комсомолец лейтенант Лесконоженко Н.Г. вылетел во главе звена ЛаГГ-3 на прикрытие войск, перебрасываемых по железной дороге в район Малой Вишеры, и на штурмовку переправы противника через Волхов. Когда наши истребители легли на курс в сторону Чудова, чтобы проштурмовать переправу, возле деревни Селищин они обнаружили 6 бомбардировщиков Ju-88 в сопровождении 6 Me-109. Набрав высоту, Лесконоженко повёл звено в атаку. Его ведомый Клочко направился в сторону истребителей, а сам он с другим ведомым М.Зуевым атаковал бомбардировщики. С первой же атаки они сбили 2 "юнкерса". Строй противника был нарушен. Клочко смог связать боем троих "мессершмиттов", а остальные набросились на Лесконоженко и Зуева. Завязался тяжёлый бой. С земли за ним наблюдал командующий 52-й армии генерал-лейтенант Н.К.Клыков. В бою Лесконоженко израсходовал все боеприпасы, но из боя не вышел. Оторвавшись от преследовавших его "мессершмиттов", он набрал высоту и сверху набросился на уцелевшие "юнкерсы". Подойдя вплотную к одному из них, он винтом отрубил противнику хвостовое опереиие. "Юнкер" рухнул на землю и взорвался на собственных бомбах. Тем временем Лесконоженко снова стал набирать высоту. За ним бросились сразу 3 "мессершмитта". Лесконоженко увернулся от пулемётных трасс, зашёл в хвост одному из преследователей и нанёс удар винтом. "Мессершмитт" загорелся и пошёл к земле. В это время в самолёт Лесконоженко попала пулемётная очередь. Он был ранен в голову и плечо. Из последних сил ему удалось покинуть повреждённый самолёт. Приземлился на парашюте возле КП армии, после чего потерял сознание. Пехотинцы доставили его в госпиталь на станции Краснянка, но спасти жизнь ему не удалось - он скончался в тот же день.

Похоронен в деревне Каменка Маловишерского района Новгородской области. На его могиле установлен памятник.

Звание Героя Советского Союза Николаю Гавриловичу Лесконоженко присвоено посмертно 27 декабря 1941 года.

Награждён орденом Ленина.