Getting a VM (VPS) is not the same as shared hosting. WIth a VM you have to install, maintain, patch and monitor everything yourself. Obviously cheap providers that offer PHP/MySQL hosting for $3 a month won't offer terrific performance, the resources will be shared with a lot of other customers, but for a simple website with maybe a shopping cart and a small catalog it's far less overhead to use shared hosting than a VM and there is a big market for that.
This being said, there are lots of cheap hosts that offer not only PHP but also Perl and Python; even Java or .Net providers can be found for $7 per month. So I'm not sure why the OP talks about $100/mo.
As for cheap solutions: OpenShift (Red Hat) has a pretty decent free tier that comes with PHP, Perl, Python, Ruby, Node.js and MySQL, but to run java it gets more expensive quickly (about $50).