Родился 16 апреля 1922 года в селе Салютоевка (ныне Краснопольский район Сумской области Украины). В 1937 году окончил 8 классов, в 1938-1939 гг. учился в школе ФЗУ при машиностроительном заводе имени Фрунзе (город Сумы) и одновременно в Сумском аэроклубе. С 1 февраля 1940 года в рядах Красной Армии, призван Сумским РВК. В 1941 году окончил Харьковское военное авиационное училище лётчиков, а в 1943 году - курсы штурманов эскадрилий.

С февраля 1943 года старший сержант Н. Н. Кононенко в действующей армии: в должности командира звена 297-го ИАП (2 июля 1944 года преобразован в 179-й Гвардейский ИАП), летал на Ла-5 и Ла-7.

11 августа 1943 года, в числе 10 Ла-5, вылетел на прикрытие наземных войск. Десятка благополучно прошла линию фронта и углубилась в тыл противника. В это время на горизонте показалась большая группа немецких бомбардировщиков под прикрытием Ме-109. Командир группы приказал шестёрке Ла-5 вступить в бой с бомбардировщиками, а остальным связать боем Ме-109. В этом бою Н. Н. Кононенко сбил один самолёт противника. Вскоре после этого боя был назначен командиром эскадрильи.

22 августа 1943 года эскадрилья Н. Н. Кононенко сопровождала бомбардировщики Пе-2, шедшие к городу Мерефе, чтобы нанести удар по скоплению войск противника. Когда пролетели над Харьковом, из облака вынырнули 16 Ме-109. Командир пошёл наперерез и перехватил их в тот момент, когда немецкие лётчики заходили в хвост "Петляковым". Завязался бой. Н. Н. Кононенко первой же очередью поджёг ведущий Ме-109. Схватка закончилась победой советских пилотов. Наши бомбардировщики провели прицельное бомбометание и возвратились на свой аэродром.

К февралю 1945 года штурман 179-го Гвардейского истребительного авиационного полка (14-я Гвардейская истребительная авиационная дивизия, 5-я Воздушная армия, 2-й Украинский фронт) Гвардии капитан Н. Н. Кононенко совершил 169 боевых вылетов, в 52 воздушных боях лично сбил 15 и в составе группы 9 самолётов противника. За эти подвиги был представлен к высшей награде страны. С марта 1945 года служил уже в 177-м Гвардейском ИАП, где летал на Ла-7.

К 9 мая 1945 года штурман 177-го Гвардейского истребительного авиационного полка (14-я Гвардейская истребительная авиационная дивизия, 3-й Гвардейский истребительный авиационный корпус, 5-я Воздушная армия, 2-й Украинский фронт) Гвардии капитан Н. Н. Кононенко совершил 193 боевых вылета, провёл 56 воздушных боёв, в которых сбил лично 19 и в составе группы 9 самолётов противника. Сражался на Брянском, Центральном, Воронежском, Степном и 2-м Украинском фронтах. Указом Президиума Верховного Совета СССР от 15 мая 1946 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 5450).

После войны продолжал службу в ВВС. В 1958 году окончил Военную командную академию ПВО. Служил в должности заместителя начальника штаба авиационной дивизии. С 19 июня 1965 года Гвардии полковник Н. Н. Кононенко - в запасе. Жил и работал в городе Белгороде. Умер 11 ноября 2000 года. Похоронен на кладбище Ячнево (в Белгороде). В посёлке городского типа Краснополье на Аллее Героев установлена памятная доска. Бюст Н. Н. Кононенко установлен на Аллеи Героев в Мемориальном комплексе "Парк Победы", расположенном в одноимённом парке в центре Белгорода.

Награждён орденами: Ленина (15.05.1946), Красного Знамени (25.08.1943, 26.10.1943, 22.02.1945), Александра Невского (29.08.1945), Отечественной войны 1-й степени (05.10.1944, 11.03.1985), Красной Звезды (26.10.1955); медалями, в том числе "За боевые заслуги" (15.11.1950).