Is it safe to use rng-tools on a virtual machine?

All of this depends on the hardware (physical or virtual) available to your VM. rng-tools can only get entropy from the sources available to it. If your virtual machine has no available sources of entropy for rng-tools to use then you'll be no better off.

Some virtualization systems are however able to make hardware sourced entropy available to guests through a number of mechanisms. In some cases you can pass a hardware device directly to your guest (USB, PCI, whatever) and have rng-tools use this device. In most cases this won't be possible.

The virtio paravirtual drivers expose various IO devices to guest VMs from the hardware controlling domain (Linux kernel running KVM, dom0 in Xen). There's a virtio-rng device that allows for an entropy source to be exposed to guests. From what I can find this is pretty mature on KVM but Xen support looks to be a work in progress: http://wiki.xen.org/wiki/Virtio_On_Xen

While virtio is great, it requires the guest have virtio drivers and thus be aware of the fact that it's a VM (paravirtualized). Newer hardware like Intel IVB and HSW chips have specific CPU instructions that provide random numbers from an on-chip RNG and these can be exposed to guest VMs. You can probe for the availability of these instructions by using CPUID.

This is a brief overview and likely information enough. If you're interested in more details there's an excellent discussion of this topic here: http://log.amitshah.net/2013/01/about-random-numbers-and-virtual-machines/

EDIT: Sorry, I guess I provided a lot of data but never really answered the question. Anyways here's my take on the actual question:

Is this safe to use (from a security perspective) on a virtual machine/virtual private server where the OS only has access to virtualized hardware? Will the generated keys be sufficiently random?

When it comes to security there's nothing more damaging than thinking your configuration is secure when it isn't. Using rng-tools when it provides you with no benefit (has no hardware entropy source source to draw from) has the distinct possibility of making you think you are generating high quality random numbers (keying material?) when in fact you aren't. So I don't think using rng-tools without having an entropy source for it in your VM will make the numbers generated any less random but it may make cause you to think you're generating high quality keys when you actually aren't.

My advice would be to use the rng-tools daemon but only after verifying that you've got an entropy source available for it to use.