I just googled for virtual server hosting and found a ton of cheap stuff. RackSpace has servers with root access for $11/month + bandwidth. Spry.com has Linux VPS servers for $33/month. ServerPoint is $30/month. Those were just the first ads I clicked on. It's more than $4, but on the other hand I can't even get hostmonster.com to load. Anyone who isn't willing to pay $30/month to have a site probably doesn't need more than static pages and CGI, although they could certainly get perl with FastCGI for $6 or so from places like GoDaddy.
I'm really not concerned about PHP. It's open source, many of my friends use it, and I don't have any problem with it succeeding.