The ONLY thing that prevents me from using Python

[D H]

I would highly recommend user-mode linux (UML) hosting, like bytemark or 
Linode: http://user-mode-linux.sourceforge.net/uses.html

Starting around the same price as average shared hosting, you get your 
own virtual linux box (i recommend debian), on which you can install 
java, mod_python, php, mono, jabber, or whatever you need.  You are no 
longer subject to the whims of the hosting provider, with respect to 
things like which version of PHP they support, or how many mysql 
databases you can create.