Родился в апреле 1912 года в городе Курган (ныне административный центр Курганской области). В 1928 году окончил 7 классов средней школы в Кургане, в 1930 году школу фабрично-заводского ученичества (ФЗУ) в Челябинске. Работал помощником машиниста паровоза. С 1 июля 1931 года в рядах Красной Армии, призван Курганским ГВК. В августе 1932 года окончил 3-ю Военную школу авиационных техников (город Пермь). Служил младшим авиатехником в 4-й Военной школе авиационных техников (город Иркутск), с декабря 1932 года исполнял обязанности инструктора, с августа 1933 года - старшего инструктора.

В январе 1934 года направлен в 1-ю Военную авиационную школу пилотов (посёлок Кача, Крым), которую окончил в январе 1935 года. Служил в строевых частях ВВС Забайкальского военного округа. Был старшим лётчиком 11-го ОАОС, 22 марта 1935 года присвоено воинское звание "старший лейтенант". С марта 1937 года - командир звена 92-го ОАОС. С апреля 1938 года - инструктор по технике пилотирования 60-й ОРАЭ, с июля 1938 года - временно исполняющий должность помощника командира эскадрильи 60-й ОРАЭ. 17 февраля 1939 года присвоено воинское звание "капитан". С марта 1939 года - помощник командира 60-й ОРАЭ. В феврале 1941 года зачислен слушателем Военной академии командного и штурманского состава ВВС КА. С 5 июля 1941 года находился в распоряжении командования ВВС Орловского военного округа. С 10 октября 1941 года - помощник начальника 3-го Отдела Управления формирования и комплектования ВВС КА.

С 12 июня 1942 года капитан Н. Д. Стародумов в действующей армии: в должности командира эскадрильи 754-м ИАП. Воевать начал на Юго-Западном фронте (в составе 220-й ИАД, 8-й Воздушной армии), летая на Як-1. 6 июля 1942 года полк был выведен с фронта на доукомплектование: в 8-й ЗИАП Приволжского военного округа (посёлок Багай-Барановка, Саратовской области), где 13 августа 1942 года был расформирован, а лётный состав передан в другие авиачасти КА.

К концу июля 1942 года капитан Н. Д. Стародумов был переведён на должность командира эскадрильи в 248-й ИАП, который проходил доукомплектование в 8-м ЗИАП Приволжского военного округа. 10 августа 1942 года полк перебазировался в Московский военный округ на аэродром авиазавода № 301 (город Химки) для получения новой матчасти. С 18 августа 1942 года приступил к боевой работе на Западном фронте (в составе 234-й ИАД и 204-й БАД, 1-й Воздушной армии), летая на Як-7Б. К середине октября 1942 года капитан Н. Д. Стародумов совершил 50 боевых вылетов, сбил в воздушных боях 7 самолётов противника лично и 3 в группе с товарищами. 16 января 1943 года ему присвоено воинское звание "майор".

С 20 февраля 1943 года боевой работы не вёл, полк проходил переформирование, затем находился в резерве (в Московском военном округе). С 28 мая 1943 года приступил к боевой работе на Брянского фронта (в составе 234-й ИАД, 4-го САК, 15-й Воздушной армии).

3 июля 1943 года штурман 248-го истребительного авиационного полка (234-я истребительная авиационная дивизия, 4-й смешанный авиационный корпус, 15-я Воздушная армия, Брянский фронт) майор Н. Д. Стародумов погиб в авиационной катастрофе. Всего совершил около 70 боевых вылетов, в воздушных боях сбил лично 7 и в составе группы 3 самолёта противника. Был похоронен в деревне Акуловские Выселки (Плавский район Тульской области), позднее перезахоронен в братской могиле города Плавска (улица Коммунаров, у здания МБОУ "Плавская СОШ № 2").

Награждён орденом Красного Знамени (05.11.1942).