Usa una base de datos embebida, que para eso están.
http://db.apache.org/derby/
Eso sí, la comunicación de los clientes con la BBDD tiene que ser a través del programa que ejerce de servidor, o al menos eso creo.
Si quisieras utilizar una base de datos de servidor, pues no te queda más remedio que instalarla aparte o con una aplicación de las que empaquetan preparar un setup de instalación. Pero esta opción no me parece nada recomendable, imagina que todo el mundo creara programas que te instalan una mysql.