It may be a little more expensive, but if you use Amazon's EC2 platform to run your virtual servers you can change IP's whenever you want. Each VPS has a dedicated "internal IP" inside EC2 (10.X.X.X) which never changes, it gets outside/internet connectivity from "Elastic IPs" that can be changed ondemand - there's even an API for it.
I've written an app that does exactly this, its running on an EC2 VPS and periodically (~36 hours) it changes its IP by first requesting a new "Elastic IP" and then assigning it to itself, releasing the previous one - the change is instantaneous. Amazon may seem expensive but you can do just about everything with their 'Spot Instances' which are 1/5th the price .. just make sure you backup your stuff incase you're Spot Price is outbid.