First issue: What type of hosting (shared, virtual, or dedicated) will meet your requirements?
Shared hosting won't work, since you require root access. Virtual (VPS) hosting can be a lot cheaper than dedicated hosting, and I don't see anything in your requirements that demands dedicated physical hardware. As of June 2011, an unmanaged (read: minimal tech support) 512 MB, KVM-based VPS starts at around ~$20/month, far lower than the cheapest dedicated hosting plans. In fact, most dedicated hosting providers wouldn't bother offering a server with as little as 512 MB of memory. (Prices do change, over time, but you can find up-to-date offerings on WebHostingTalk [see below].)
The cheapest VPS providers usually use OpenVZ/Virtuozzo. In my experience, OpenVZ/Virtuozzo also makes it easy for less-than-ethical providers to over-sell their hardware. Some providers offer Kernel Virtual Machine (KVM) solutions, which are generally more expensive because it's harder to get away with under-provisioning memory.
Second issue: How can you choose a good hosting provider?
I don't want to comment on any specific virtual hosting providers, here, but I will warn you that there are some TERRIBLE hosting companies in the market, today. VPS hosting is a cutt-throat business, and the profit margins are razor thin, so there is a lot of pressure on providers to cut corners. It's difficult to tell the difference between good and bad providers, and sometimes a good hosting company will go bad, due to changes in management or policy. (I've had this happen to me, a couple of times.)
In order to weed out the worst VPS providers, I would encourage you to spend some time reading the reviews, complaints, etc. on http://www.webhostingtalk.com/ (WHT). There are a lot of horror stories on there (including some of mine), but the volume is high enough that you should be able to get a pretty fair look at your options. The forums are mostly English-speaking, with plenty of UK representation, so you shouldn't have too much trouble finding a provider in your own country.
Also, one of WHT's sub-forums is dedicated entirely to hosting provider offers. You'll find coupon codes for discounts, or other special offers, etc.
In my opinion, Amazon's EC2 would not work very well for you. (All due respect to the other poster who suggested it.) EC2 is a very "do-it-yourself" service. In my experience, it takes more technical know-how to get an EC2 instance running than an un-managed VPS instance, since most VPS providers have turn-key images with common hosting control panels, etc. pre-installed.
In fact, I would suggest that you consider whether you want to spend the money on a managed hosting plan. Most VPS providers have some kind of full-service, managed option. If you're not confident that you can handle setting up and running your own server, the extra support might be worth the money.