Родился 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 г. от партии КПРФ по федеральному округу. Был выдвинут под десятым номером общефедеральной части списка кандидатов, однако после исключения из нее Павла Грудинина фактически занял девятое место в общей части списка. Первый заместитель руководителя фракции КПРФ Геннадия Зюганова.
С 12 октября 2021 г. - первый заместитель председателя комитета Госдумы по труду, социальной политике и делам ветеранов.
Член редколлегии газеты "Советская Россия".
Отмечен благодарностью президента РФ (2013).