My current way to get around this is to replace /dev/random with the /dev/urandom device, which does not block if the entropy pool is depleted:
mknod /dev/newrandom c 1 9 chmod --reference=/dev/random /dev/newrandom mv -f /dev/newrandom /dev/randomThis has the consequence that the "randomness" these commands use doesn't have as much "real" entropy, though some operating systems (like FreeBSD) have a non-blocking /dev/random by default (and it's also questionable what "real" entropy means for a virtual machine in the first place).
I'm also using cowbuilder within these VMs to do package builds. But cowbuilder has its own /dev tree, with its own device nodes, so this needs to be fixed too. So after you have successfully done cowbuilder --create, you need to modify the random device within the cowbuilder chroot:
mknod /var/cache/pbuilder/base.cow/dev/newrandom c 1 9 chmod --reference=/var/cache/pbuilder/base.cow/dev/random /var/cache/pbuilder/base.cow/dev/newrandom mv -f /var/cache/pbuilder/base.cow/dev/newrandom /var/cache/pbuilder/base.cow/dev/randomHopefully this will be useful for other people using cowbuilder (or other build strategies) on isolated virtual machines. If you've worked around this problem in other ways (or if there's a security concern about this approach), i'd be happy to hear about the details.