Родился 1 сентября 1956 г. на хуторе Проциков Багаевского района Ростовской области.
Среднее специальное образование получил в Сальском сельскохозяйственном техникуме (г. Сальск Ростовской области). В 1984 г. заочно окончил Ростовский институт сельскохозяйственного машиностроения по специальности "инженер-механик" (ныне Донской государственный технический университет), в 1996 г. - Академию народного хозяйства при правительстве РФ (ныне Российская академия народного хозяйства и государственной службы при президенте РФ) по специальности "менеджер-экономист".
С 1977 г. работал на ростовском комбайностроительном заводе "Ростсельмаш", где был слесарем-испытателем, инженером-технологом, мастером, механиком, заместителем начальника цеха и начальником цеха.
В 1980-х - начале 1990-х гг. был инструктором промышленно-транспортного и социально-экономического отделов Ростовского городского комитета Коммунистической партии Советского Союза (КПСС). Затем - начальником производства в научно-производственном объединении "Микротехника" (Ростов-на-Дону).
В 1994-1997 гг. - депутат Законодательного собрания Ростовской области I созыва.
12 декабря 1995 г. баллотировался от Коммунистической партии Российской Федерации (КПРФ) в депутаты Государственной думы II созыва. В Думу не прошел.
Со второй половины 1990-х гг. по 2002 г. занимал пост первого секретаря Ростовского городского комитета (горкома) КПРФ.
В 1997-1999 гг. - депутат Государственной думы II созыва. 1 июня 1997 г. избран от КПРФ на дополнительных выборах по Пролетарскому одномандатному округу №145 (Ростовская область). Набрал 37,57% голосов избирателей, его ближайший соперник – Геннадий Меликьян, бывший министр труда и социального развития РФ, выдвинутый проправительственным движением "Наш дом – Россия" - 20,77%. Занял в Госдуме место депутата от Партии российского единства и согласия Сергея Шахрая, который отказался от мандата, в связи с переходом на работу в Администрацию президента РФ. Николай Коломейцев был членом фракции КПРФ, с сентября 1997 г. вошел в состав комитета Госдумы по промышленности, строительству, транспорту и энергетике; с 1998 г. – заместитель председателя комитета по регламенту и организации работы Государственной думы.
В 1999-2003 гг. – депутат Государственной думы III созыва. 19 декабря 1999 г. избран по списку КПРФ, был четвертым номером в Кубанско-Донской региональной группе (республики Адыгея, Ингушетия, Чечня; Краснодарский край; Ростовская область). Член фракции КПРФ, заместитель председателя комитета по регламенту и организации работы Государственной думы.
В декабре 2000 г. баллотировался на пост мэра Ростова-на-Дону от КПРФ, однако с результатом 37,14% голосов избирателей занял второе место. Победитель – действующий глава города Михаил Чернышев, набравший 50,04%.
С января 2002 г. - первый секретарь Ростовского областного комитета КПРФ, член ЦК КПРФ. Сменил на этом посту Леонида Иванченко.
7 декабря 2003 г. баллотировался в Госдуму IV созыва по Пролетарскому одномандатному округу №145 (Ростовская область). В Думу не прошел, набрав 30,82% голосов избирателей. Победу в округе одержала замгубернатора области, супруга мэра Ростова-на-Дону Зоя Степанова (самовыдвиженец; 32,09%). Николай Коломейцев обратился в суд с иском об отмене результатов выборов из-за имевшей место, по его мнению, фальсификации их результатов. Однако судом выборы были признаны законными.
19 декабря 2004 г. во второй раз участвовал в выборах мэра Ростов-на-Дону, был выдвинут КПРФ. Набрал 20,23% голосов избирателей, проиграв действующему градоначальнику, самовыдвиженцу Михаилу Чернышеву (65,69%).
В 2007-2011 гг. – депутат Государственной думы V созыва. 2 декабря 2007 г. избран по списку КПРФ, возглавлял региональную группу №65 (Ростовская область). Входил в партийную фракцию, был членом комитета Госдумы по труду и социальной политике.
2 марта 2008 г. был избран от КПРФ в Законодательное собрание Ростовской области IV созыва, возглавлял партийный список. После выборов отказался от депутатского мандата.
С ноября 2008 г. по настоящее время - член президиума ЦК КПРФ.
В 2011-2016 гг. – депутат Госдумы VI созыва. 4 декабря 2011 г. избран по списку КПРФ (первый номер в региональной группе №56, Ростовская область). Был членом фракции КПРФ, заместитель председателя комитета Госдумы по труду, социальной политике и делам ветеранов.
8 сентября 2013 г. избран в Законодательное собрание Ростовской области V созыва по списку КПРФ, после выборов отказался от мандата.
14 сентября 2014 г. возглавлял список КПРФ на выборах в Государственного совета Республики Крым I созыва. Избран не был, т. к. партия не преодолела 5-процентный барьер.
13 сентября 2015 г. баллотировался на выборах губернатора Ростовской области от КПРФ. С результатом 11,66% голосов избирателей проиграл действующему губернатору Василию Голубеву (78,21%).
В 2016-2021 гг. – депутат Государственной думы VII созыва. 18 сентября 2016 г. избран по списку партии КПРФ (первый номер в региональной группе № 33, Ростовская область). Также баллотировался по Таганрогскому одномандатному округу №151, набрал 20,97%. Проиграл единороссу Юрию Кобзеву (46,70%). Первый заместитель председателя думского комитета по труду, социальной политике и делам ветеранов. Первый заместитель лидера фракции КПРФ Геннадия Зюганова.
С 2021 г. - депутат Государственной думы VIII созыва. Был избран 19 сентября 2021 г. от партии КПРФ по федеральному округу. Был выдвинут под 10-м номером общефедеральной части списка кандидатов, однако после исключения из нее Павла Грудинина фактически занял 9-е место в общей части списка. Первый заместитель руководителя фракции КПРФ Геннадия Зюганова. С 12 октября 2021 г. - первый заместитель председателя комитета Госдумы по труду, социальной политике и делам ветеранов.
Член редколлегии газеты "Советская Россия".
Отмечен благодарностью президента РФ (2013).