Check out vps.net. They take a few minutes to come up, but are billed by the minute. However, when you create a vm, they bill you for the remainder of the month up front. When you destroy the vm, you are given an account credit for your unused time.