Root into a virtual machine (KVM)

Scenario: I have a KVM virtualization server with a number of VMs defined. Suddenly, I cannot log in as root to one of the VMs. I will need to reset the root password. The "normal" methods like adding single or init=/bin/bash to the kernel boot line in GRUB do not work. The only option left is to boot from a rescue disc, but this is a virtual machine -- there is no DVD drive. Oh, no -- what to do?

NEWS FLASH: I just learned from a colleague that there is a much easier method. It is possible to chroot directly into the VM from the virtualization host. Will post detailed instructions as soon as I get them. Until then, there is always the "long route" described below.