Little is known of the specifics in the Bitcoin-related Linode security incident. This was all that was released: http://status.linode.com/2012/03/manager-security-incident.h...
This. (Disclaimer: I'm not connected to prgmr.com, other than being a satisfied customer for years.)
You can get VPS's small as you need, with pricing to match. Great for bootstrapping on a shoestring.
You can use whatever distro you want -- Ubuntu, Debian, CentOS. You can use whatever version of that distro you want -- you can do an OS upgrade or downgrade whenever you want.
The tech support is friendly and competent. The owner's willing to personally talk to customers.
If you're knowledgeable, the tools to do almost anything you need are included. If you know how to fix something, the out-of-band console will let you handle almost any issue remotely. For example you can reboot in single-user mode or even initramfs. In contrast, many other hosts use half-baked web UI's and/or require filing a support ticket, with hours or days of turnaround, for even simple issues.
It's really flexible. You can use Ubuntu or Debian if you want to get up and running quickly. You can use LVM to make backups easy. You can install BSD. You can even install a custom kernel -- just about anything with Xen guest patches will work.
The only downside (based on your stated preferences) is that it's US-based.
They're not in the UK, but in France... Git is "being implemented, and will be released in the next version of the website."
If you have any real technical ability a VPS is an excellent option.