Родился 15 июля 1921 в деревне Выхино (ныне в черте Москвы). Окончил 7 классов и школу фабрично-заводского ученичества (ФЗУ) при московском заводе "Серп и молот" (сегодня колледж связи № 54 имени П. М. Вострухина), затем работал токарем и аппаратчиком-электриком на этом заводе. В 1937 году поступил без отрыва от производства в аэроклуб Пролетарского района Москвы, который окончил в 1939 году. С 18 марта 1940 года в рядах Красной Армии, призван по специальному набору Ухтомским РВК (Московской области). В 1941 году окончил Борисоглебскую военную авиационную школу пилотов и был оставлен в ней лётчиком-инструктором.

С 20 октября 1942 года младший лейтенант П. М. Вострухин в действующей армии: в должности старшего пилота 271-го ИАП (18 марта 1943 года преобразован в 64-й Гвардейский ИАП). Летал на Як-7Б (некоторое время на самолёте "Балашовский колхозник"). С 22 октября 1942 года приступил к боевой работе на Калининском фронте (в составе 274-й ИАД, 1-го ИАК, 3-й Воздушной армии). С 27 февраля 1943 года воевал на Северо-Западном фронте (в составе 6-й Воздушной армии).

К 17 марта 1943 года старший лётчик 271-го истребительного авиационного полка (274-я истребительная авиационная дивизия, 1-й Гвардейский истребительный авиационный корпус, 3-я Воздушная армия, Калининский фронт) младший лейтенант П. М. Вострухин совершил 83 боевых вылета, участвовал в 28 воздушных боях, сбил лично 12 и в группе - 3 самолёта противника. Указом Президиума Верховного Совета СССР от 1 мая 1943 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 928).

С 3 апреля 1943 года боевой работы не вёл: полк находился в Резерве Ставки ВГК в Московском военном округе (город Люберцы), занимался по плану учебно-боевой подготовки. С 9 мая 1943 года приступил к боевой работе на Брянском фронте (в составе 15-й Воздушной армии).

19 июля 1943 года командир звена 64-го Гвардейского истребительного авиационного полка (4-я Гвардейская авиационная дивизия, 1-й Гвардейский истребительный авиационный корпус РСВГК, 15-я Воздушная армия, Брянский фронт) Гвардии лейтенант П. М. Вострухин погиб в воздушном бою у деревни Алёшня (Залегощенского района Орловской области). По воспоминаниям Героя Советского Союза Муравьёва Павла Игнатьевича "после боя сел на вынужденную, вышел из самолёта и попал под миномётный обстрел". К тому времени выполнил более 100 боевых вылетов, провёл более 40 воздушных боёв, сбил лично 16 и в составе группы 3 самолёта противника (в последнем наградном листе говорится о 16 личных и 4 групповых победах).

Похоронен в селе Моховое в школьном саду. На могиле Героя установлен бюст. Также бюст и мемориальная доска установлены на улице его имени в Москве. На территории завода "Серп и молот" установлен памятник. Имя Героя носят Московский колледж автоматизации и радиоэлектроники № 27, оздоровительный летний лагерь московского завода "Серп и молот", улицы в Москве и в селе Моховое. На здании Московского государственного вечернего металлургического института установлена мемориальная доска.

Награждён орденами: Ленина (01.05.1943), Красного Знамени (06.02.1943, 19.07.1943), Отечественной войны 2-й степени (23.02.1943), Красной Звезды (19.03.1943).