All VMs run as the same user...

In addition to using one UID per KVM instance, use the new native container features in Linux to put each KVM into its own container. With an extremely limited view of the filesystem, namespaced process tables and IPC, an empty capabilities bounding set and appropriate iptables OUTPUT rules, breaking out of the VM into the KVM process does an attacker no good. No SELinux necessary.

With such a setup, the only thing you have to pray for is that there are no vulnerabilities that allow a guest VM to break into the host's ring 0. Unfortunately, such bugs have already been discovered in Xen.

(I can share my C wrapper for containerizing KVM if anybody's interested. Post a followup to this comment and I'll tar it up and post it somewhere.)