Вырос в деревне. В 1943—1946 занимался в московской изостудии ВЦСПС. В пятидесятые годы зарабатывал на жизнь как оформитель и плакатист. В 1957 поступил в Московский государственный художественный институт им. В. И. Сурикова (вскоре был исключён за несогласие с принципами соцреализма). C 1965 участвовал в зарубежных выставках (США, Польша, Италия, Франция). Член «Лианозовской группы», сложившейся в середине 1960-х вокруг Евгения Кропивницкого. Активно участвовал в приватно-квартирных и публичных выставках авангардного искусства, в том числе — в «бульдозерной выставке» (1974). С 1990-х годов чаще всего живёт в Германии, постоянно приезжая в Россию
Развил своеобразный вариант информеля, сделав картину не столько изображением, сколько предметом. Отсюда тяготение Немухина к контррельефу, а позже, в 1980-х, к трёхмерным композициям. Сквозной мотив немухинской живописи — карточная колода (метафора игры).