Может БОМЖ восстановить паспорт (без наличия каких либо документов)?

Ему необходимо обратиться в отдел ФМС по месту его проживания.
1. Если он когда-либо получал паспорт и просто его потерял, то будет заведено дело об утрате паспорта. По временному удостоверению личности, выданному в ФМС, он получит в ЗАГСе дубликаты необходимых документов.
2. Если он вообще никогда не получал никакого паспорта, тогда в ФМС будет проводиться установление его личности и определения принадлежности к гражданству РФ. Если установят, что он гражданин РФ, его документируют паспортом. Если нет - посоветуют, в посольство какого государства обратиться (если окажется, что он является гражданином иного государства) , или документируют удостоверением личности лица без гражданства ( если невозможно определить его принадлежность к гражданству какой-либо страны) .
В общем - в ФМС, а там разберутся.

Полиция ему в помощь.

сходить в загс где родился. подтверждение двоих. дадут свидетельство о рождении. потом как обычно.

нужно обязательно свидетельство о рождении для восстановления (хоть бомж, хоть не бомж) . а вот в загсе чтоб поверили, нужно появиться с такими людьми, свидетельство которых об этом человеке работники загса обязательно учтут (например, представители власти районного или сельского уровня и т. п.)

Запросто если не будет врать про старые паспортные данные

придется побегать по всяким конторам, но теоретически это возможно... хотя и практически тоже..