I’m also trying to setup MySQL bindings in a virtualenv. All I had to do was install the package that contains mysql_config. On Ubuntu it’s called libmysqlclient-dev.
After that I was able to do a (virtualenv’d) python setup.py build and python setup.py install.