Try Google AppEngine. It's free, very easy deployment, and allows Django (minus some things like database) or roll-your-own python against their web API.

Thanks. I was actually reminded of Google App Engine after following wmorein's link to web.py, and then thought about using their webapp framework instead of Django.