Amazon micro EC2 instances are reasonably priced and I use one for my personal sandbox and mail server.
Average price is $14.60
/month ($0.02/h * 24h * 365d / 12) for a no commitment a la carte and drops to an average of $8.82/mo or $6.43/mo with 1 or 3 year reservations https://aws.amazon.com/ec2/#pricing
. They also have a free for the first year program at http://aws.amazon.com/free/
to get you started.
You won't get KVM access for OS install but there are startup images for all the common free linux distros (Centos, Fedora, Debian, Ubuntu, etc.), Amazon Linux (a custom distro for EC2), and non-free OS's like RHEL and MS Windows (they cost more per hour). Every distro I've used on there gives you either direct root login or `sudo su -l` capability. You have full control over the incoming firewall rules so you can allow specific ports by IP or CIDR range without chewing up CPU or I/O in iptables. You can add additional storage on the fly (including via automated script within your VPS if you can program) and take live snapshots of running disks (including the OS disk) for backups.
I use Amazon for my work systems and much prefer them to managing an on site rack or letting some other host charge us for the impediment to administration that is managed hosting.