Seems like a good use-case for docker
We used LXC for this, but that or docker is probably a sane approach. You get some (not all) of the separation you do from VMs with all the scarce resource requirements of different users. If you consider the implications carefully, you can even give users root inside these containers in certain circumstances.