Just because a hosting service doesn't list Python on their web page doesn't mean that it's not available. My company's service (LunarPages) supports Python, and only recently has it started appearing on their online literature.
Once you find your service based on price/support/etc., send them an e-mail asking for Python support. The worst they can say is "no, and we never will," but just as likely they might respond "yes, it's already there" or "yes, we can add that". -- Paul -- http://mail.python.org/mailman/listinfo/python-list
