Shared web hosting providers? I don't think so. I'd say in the low hundreds of all shared web hosts do, but not thousands. And of those, very few will offer any support. On the other hand, PHP comes with every single shared hosting installation that exists. I don't know of one that doesn't offer PHP support because it comes standard with... CPanel.

From PHP.net -- "Today, PHP is being used by hundreds of thousands of developers (estimated), and several million sites report as having it installed."