I've recently start renting a dedibox SC at online.net, a french provider. I chose the cheapest box, but still, I have a real bare metal server for 6€/month (around 8.80$ I think). They provide standard base images, but as you're running on real hardware, abd can boot from rescue live images, it's easy to bootdtrap a new system: http://blog.z3bra.org/2015/08/install-al...nenet.html.

The SC box doesn't have it, but all others provide a KVM over IP, which can also help for traditional installations.
Their services seems pretty good so far. tickets get answered in less than 10 minutes, and they also have their own IRC server for support.