For Qemu 1.3 and later, there is VirtIORand where you can have VMs attach to a HWRNG on the hypervisor, then food that into the kernel CSPRNG. This should be imaged by default, so on first boot, each VM has enough entropy for key generation.
On Ubuntu, pollinate solves this problem: http://blog.dustinkirkland.com/2014/02/random-seeds-in-ubunt...
I have VM images begin without ssh host keys and have a service dependency on haveged: http://www.issihosts.com/haveged/ and http://security.stackexchange.com/questions/34523/is-it-appr...