1. Rent a cheap box at http://hetzner.com (32GB RAM/59€ per month; 64GB RAM/109€ per month) or http://OVH.ca/.
2. Install Proxmox VE 2.0 from http://proxmox.com/products/proxmox-ve Create virtual instances via RESTful API on demand: http://pve.proxmox.com/wiki/Proxmox_VE_API
3. use chef or puppet.
=> unbeatable price/value and it's up to you if/how you lock into technologies/abstractions/dynos/...
If you need speed it will cost you more for 15K SAS disks w/ a sizable battery backed RAID controller, but it will be worth every cent.
You don't want to put too many VMs on them or you'll quickly go through your IO bandwidth.
This is the problem so many devs don't understand. You run out of IOPS for your DB and your app is going nowhere. Managing storage in a reliable, fast and cost effective manner isn't easy.
Consumer SSDs are starting to change that, but you will be still struggling to find many dedicated server offerings backed with SSD storage, and there are still questions about long term reliability (4 years or so) which is typically the period your leaving hardware provisioned for to pay it off.
You'll have to know precisely what you want/how to configure the machines, but otherwise its perfect. Exactly what oyu'd expect for unmanaged hosting.
Incero.com
Mind you its all a compromise, if you know that disk IO isn't a factor for your application then servers like that are ideal. I just won't run a large database on it without something like MySQL Cluster using a Memory table. It would require 2 servers, but REALLY good performance, good reliability (just get 2 dual PSU servers in different cabinets).
http://reliablesite.net/v4/ their twitter account has big discounts
maybe only 4x more expensive, and they don't charge a monthly fee for a private network.