The good news is that many inexpensive shared hosts support Python.
The great news is that following this article you should be able to get a pure Python CGI script running and then install the custom packages required to use one of the nice Python web frameworks.