There is no any single doubt that KVM based virtualization is best as hardware is utilized much efficiently.
There are lots of software in market (free and paid) to ease the process of virtualization like Proxmox, Vmware, VirtualBox, etc.
I would suggest you to go though these first before digging into know how of automatic VPS provision.
Your concern regarding billing system is not clear to me. You can integrate Whmcs on your website for billing.