Are you doing this for security reasons? Because if you are, then having your DB on a separate publicly-accessible network sorta defeats the purpose. The idea of keeping web server and DB server on separate servers is so that, while your web server needs to be in a DMZ, your database server should not.
The best thing to do is just find a web host that puts the DB on a separate server, but one that is only accessible from within the network. I don't know of any web hosts like this off hand though.
If you want to separate DB and application for other reasons, then DremaHost offers shared hosting with unlimited MySQL databases, which are hosted on separate servers. Still, even though I like DreamHost and recommend them to everyone, I don't know if this is any reason to switch web hosts.
If you want more scalable database access, then you could try Amazon's SimpleDB or Amazon Relational Database Service (RDS). Both offer cloud data storage; the latter includes a MySQL option, I believe.