Родился 7 (20 февраля) 1909 года в Москве. Отец Поликарп Андреевич — парикмахер, мать Антонина Ильинична — домохозяйка. Окончание школы совпало с концом НЭПа в 1927—1928 годах: парикмахерскую у отца отобрали, надо было зарабатывать и помогать семье. В. Мартыненко был разнорабочим, грузчиком, затем устроился в конструкторское бюро ВНИИТМАШ, которое находилось на Никольской улице (улица 25 Октября).
В 1932 году участвовал в проектировании и строительстве Сталинградского тракторного завода. Спроектировал устройство для транспортировки труб: длинная труба подвешивалась сбоку трактора, равновесие обеспечивалось балластом, помещённым между гусеницами. Такой тип трубоукладчика использовался до 1990-х годов.
Начинал учиться в Московском горном университете, в Текстильном институте, в частном институте Каган Шапшая, однако обучение прерывалось по причине «мелкобуржуазного происхождения». В 1934 году поступил на вечернее отделение Московского электромеханического института инженеров транспорта, который окончил в 1938 году. Во время учёбы продолжал работать в ВНИИТМАШе. В это время он вместе с Л. С. Вилициным создал снегоуборочную машину, подающую собранный снег по ленточному транспортёру в кузов автомашины.
10 октября 1939 года был призван в РККА и направлен в Польшу. Получив контузию, 2 ноября 1939 года был возвращён в Москву в «Гормашпроект». 22 ноября 1939 года переведён в 4-е главное управление оборонной промышленности на должность инженера-конструктора.
22 октября 1941 году командирован в Челябинск на Челябинский тракторный завод (завод № 78, потом завод № 200) на должность дежурного по производству для налаживания выпуска танков. В 1943 переведён на завод № 40 на должность ведущего инженера. Трудился на оборонных предприятий до 1945 года.
В 1945 году возвратился в Москву. Проработав короткое время в Наркомате среднего машиностроения, 27 марта 1945 перешёл на работу в Гипроуглемаш — головное предприятие министерства угольной промышленности по механизации добычи угля. За 2—3 года создал первый угольный комбайн ВПМ-1, который испытывался и отлаживался в Донбассе, а затем был внедрён на многих шахтах, включая Карагандинский угольный бассейн.