Sad part is mysql doesn't have an async C API. Probably a good reason to use postgres. Although one could fake it using pthreads like libeio does for files.
If you run python instead on your server, it will be slower, but you can use twisted, gevent, stackless, etc., and don't need to care that mysql blocks. However, that doesn't solve your clientside issues.
