Virtual machines have virtual hardware, but this does not necessarily means that they are completely devoid of entropy sources. In particular interrupts: while the VM has no real interrupt generator hardware, its OS still receives such "interrupts" as part of the emulation of hardware. For instance, when you connect to your VM through, say, SSH, network packets still flow back and forth, and each incoming packet triggers an emulated interrupt in the VM. The entropy derived by the kernel from such an interrupt comes from the exact time of appearance of that interrupt, which, in this case, is a function of the real arrival of the packet on the physical network interface of the host system. The process from incoming packet to interrupt is more convoluted than in a non-virtual machine, since the host and the VM layer lie in between, but entropy from the physical world is still made available to the VM kernel.
A much more pressing problem for VM and randomness is VM cloning. You may want to install and configure a complete VM, then make a snapshot and clone it in order to easily create several new already configured VM. Unfortunately, this means that all the clones start from the exact same internal RNG state. Once booted, they begin to diverge as each accumulates its own "random events" (even though the hardware is emulated, emulated hardware events still indirectly come from true hardware random events, as explained above). The divergence may be slow in computing terms (it could take several seconds, and that's very long for computers that can do billions of operations per second).
The most complete method to fix that is to enforce randomness by seeding each VM with a seed obtained from some other random source elsewhere; this is as easy as writing some file into
/dev/random. This may be desirable if you clone VM; otherwise, this is probably useless (but it won't harm anyway). Note that this is needed only once per VM: normal Linux distributions will generate and save a "seed file" upon shutdown and reuse it at next boot, so once a VM has been seeded it stays seeded.
As for your #2 solution, take note that the difference between
/dev/urandom (in Linux) is not exactly what you state.
/dev/random will block if it estimates that its internal pool has not enough entropy; but it also consider that its pool is depleted upon usage. Blocking before enough entropy has been gathered is fine; but the "depletion effect" implies a lot more blocking, and that one has only very flimsy scientific basis. It is a known defect of Linux's
/dev/random. A much saner behaviour is what you get with FreeBSD's
/dev/random (and, by extension, Mac OS X): that one will block until enough initial entropy has been gathered, then it will produce as many bytes as you wish with a cryptographically secure PRNG, without blocking. Note that FreeBSD
/dev/urandom are completely identical (and this is good).
Anyway, even Linux's
/dev/random maniacal behaviour with regards to entropy depletion will be fooled by VM cloning. So insisting on generating keys with
/dev/random will not only make you wait for inordinate amounts of time; it may also fail to actually achieve the desired level of randomness in the presence of VM cloning.
To sum up, your #3 solution is the right one.