OpenStack is your best shout. But if you want to provide VPS in particular too, your clients will want a good management panel, look at OnApp.
There is honestly no point in doing cloud on the cheap, because you aren't actually creating a cloud offering when you boil down to the details. The last thing you want to do is disappoint customers because of an under delivering product, it's a quick fire way to tarnish your brand.
If you aren't going to spend the right amount of money on the infrastructure, just don't do it. If you want to sell Cloud Web Hosting, then there's a good number of quality reliable cloud server providers that you can turn to. Some even allow you to resell cloud VPS.
You can consider cloudstack or Openstack. Is quite complete. For cloud, it is almost zero downtime , and no single failure .
▀▄ GigsGigs.com - Asia, Hong Kong, Singapore, Malaysia 1Gbps Dedicated Server
▀▄ GigsGigsCloud.com - Asia, Hong Kong, Singapore, Malaysia 100Mbps VPS ** We welcome BGP Peering and AnyCast Provider **
It is definitely possible to accomplish that. You could actually accomplish that with 1 server and add more servers as you grow. You wouldn't have any failover with a single, but it can be done. It can be accomplished with XEN or KVM or LXC, all open source.
We have built a number of private clouds for our customers using Proxmox (KVM and LXC). Clouds range in size from single servers to 10+ nodes on shared SANs.
It appears you are just beginning with this type of setups, so CloudStack would be good to go with, but you have to work on the cost involved in, as your setup is a smaller one because you would not want to end having to do more investments than return from it.