I assume you've looked at Amazon EC2? They offer VMs at a wide variety of price/performance points.
There are cheaper options, but they all involve a lot more work, IMO (especially if you may need to deploy and remove servers regularly, as it sounds like you might).
Edit: they have a free tier, which may be enough to get you started.