MySQLdb is what I have used before.
If you host is using Python version 2.5 or higher, support for sqlite3 databases is built in (sqlite allows you to have a relational database that is simply a file in your filesystem). But buyer beware, sqlite is not suited for production, so it may depend what you are trying to do with it.
Another option may be to call your host and complain, or change hosts. Honestly these days, any self respecting web host that supports python and mysql ought to have MySQLdb pre installed.