There is little known provider of virtual linux servers http://www.openhosting.com (CentOS instance with root access for as little as $20 a month ).

I have been using them since early 2004. Nice experience.

Author of http://modpython.org is their founder, so presumably they know a thing or two about web applications.