If you want a cheap server then most likely it'll sit near-idle most of the time and you could make do with a Virtual Dedicated Server, aka VDS or VPS (Private.) On a proper VDS you'll get full root access and, essentially, the machine is exactly equal to a dedicated server. You just can't fiddle with the kernel. So you have all the flexibility, etc.
Multiple VDSs are squeezed into one physical server, so for example you can purchase a VDS with say 256Mb RAM, 20Gb disk space, etc. They're really good if you just need the flexibility but not all the power, and price is important.
They're also normally hosted on top-end hardware so you should get decent performance
We use 2host.co.uk who start at around £19.99/mo + VAT. Pretty darn good value for money if you ask me