Hoy en día hay diversos proveedores de cloud que ofrecen servicios en los que podrías tener una base de datos. Por ejemplo Heroku, o Amazon AWS con su free tier.
En estos servidores podrías tener MySQL sin problemas. Pero estos servicios gratuitos, aunque ofrecidos por plataformas muy profesionales, no se deberían usar en proyectos comerciales, sino más bien en temas que sean personales, pruebas de concepto y cosas así. Al final, si quieres un servicio profesional, con disponibilidad constante, entonces te toca pasar por caja y pagar.
Hay lugares como Gigarocket que dicen que ofrecen VSP gratuitos, donde podrías instalar MySQL, pero no te lo recomiendo porque seguro que darán problemas. Por 2 euros al mes podrías tener un servicio básico en algunos proveedores como OVH, que tampoco serán los mejores VPS del mundo a ese precio, pero al menos si pagas te aseguras que tendrás el servicio activo y funcionando siempre.