While this is an old question, I'm currently looking for the same, and wanted to share this post in which a developer uses DigitalOcean's lowest-end server (512MB, 1-core) which costs only $5/mo. I haven't tried it myself yet (still exploring), but I figure if the $5/mo server works, then even if it's a bit too slow for my needs, the next model is $10/mo -- the same as Atlassian's own hosting but allowing full freedom & flexibility of your own server. On the whole I'm trying to shoot for < $10 for just that reason.
Others I've found:
- DataShack - 512MB at $4/mo
- [Linode] - 1GB at $10/mo (what [EEAA] suggested above)
- [Mozy] - Doesn't give specs, though. Actually found it via an add on this very page!
I'd post the links to the above services, but apparently ServerFault won't let me because I'm too new. Naturally.
I'll update this if I find anything better.