Родился в крестьянской семье. Русский. Окончил 4 класса, работал плотником и пимокатом в колхозе.
В августе 1941 года был призван в РККА и направлен на фронт. Воевал сапёром в составе 33-го гвардейского отдельного моторизованного инженерного батальона 3-й гвардейской моторизованной инженерной бригады 4-й гвардейской танковой армии (1-й Украинский фронт). Был дважды ранен.
Гвардии ефрейтор П. А. Шихов отличился в боях под Берлином весной 1945 года. 27 апреля он первым переправился через реку Хафель в районе города Потсдама и вступил в бой. По собственной инициативе заменив выбывшего из строя командира взвода, П. А. Шихов с бойцами успешно атаковал первую траншею и, проявив мужество, поднял взвод в атаку на вторую линию траншей. Фашисты встретили наших солдат с фронта и флангов автоматно-пулемётным огнём, фаустснарядами и гранатами. Потом завязался рукопашный бой. В итоге бойцы во главе с П. А. Шиховым сумели вытеснить фашистов из второй линии обороны. Как свидетельствует наградной лист, взвод в рукопашной схватке уничтожил 30 гитлеровцев. 9 из них были на счету самого Шихова.
1 мая 1945 года, прочёсывая лес у населённого пункта Цаухвиц, П. А. Шихов наткнулся на большую группу фашистов. Открыв по ним внезапный огонь и уложив несколько из них, заставил остальных сдаться в плен.
Указом Президиума Верховного Совета СССР от 27 января 1945 года за образцовое выполнение заданий командования в борьбе против немецко-фашистских захватчиков и проявленные при этом мужество и героизм Шихову Павлу Андреевичу было присвоено звание Героя Советского Союза с вручением Ордена Ленина и медали «Золотая Звезда» ( 6676; записи: 150037249).
Демобилизовавшись, после войны вернулся домой в деревню Лобачи Куменского района Кировской области, работал в колхозе.
В 1960 году переехал жить в Омскую область с первой группой первоцилинников во вновь создаваемый совхоз "Целинный". Работал плотником на втором отделении совхоза. За доблестный труд на целине удостоен ордена "Знак Почета" и медали "За освоение целинных и залежных земель".
Награжден орденами Ленина (27.06.1975) и Красной Звезды (27.01.1945, записи: 23237444), медалью «За победу над Германией в Великой Отечественной войне 19411945 гг.» (09.05.1945) и другими медалями.
Скончался 8 ноября 1961 г. Похоронен в селе Целинное Русско-Полянского района Омской области. На могиле Героя установлен надгробный памятник.
Имя Героя высечено золотыми буквами в зале Славы Центрального музея Великой Отечественной войны в Парке Победы (Москва).
В 2019 году имя Героя выбито на гранитной стеле на Аллее Славы в парке Победы города Кирова.