I've had very good success with http://portland.co.uk. They offer PHP, Perl, SSI, and, yes, MySQL support (1 db). They give you 15 MB of web space as well. No banners/popups. Completly free, and they also offer full truly free domain hosting.
I've had good results, with good uptime and support. To enable MySQL, sign up for an account. Wait for the confirmation e-mail and then go to the support section and "request" a MySQL account. Install phpMyAdmin (or another admin utility) and you're ready to go.
Good luck.