I also recommend to have a demo server, to which you can push your latest changes without thinking twice. This way, demoing new features to the customer or testing your deployment script does not change the staging box.
This way you can have your staging deploy be a much more realistic test run of your production deploy. You only push to staging, when you are about to push to production. Otherwise you might get state differences between the two like outstanding migrations that need to be run on one server but not on the other one. Typically things like that beak you neck during deployment to prod, so you want to test that. But you still want to have a faster way of getting features vetted by your customer. So you should have demo and staging.
One of the nice things about being on the cloooooooooooud is that, if you've got your infrastructure managed right, a developer who wants a sandbox -- for any reason -- should be able to get one with about as much difficulty as getting office paper, and be able to bin it with about as much regret.
If you're hosting with Amazon and your application data is on its own EBS (block storage service) volume cloning your environment is easy. You can snapshot the volume, create a new volume from the snapshot, and spin up a new server (you automated provisioning, right?). That way you get a near exact replica of your environment with not too much work.
This is what we have with an Oracle product:
Vanilla - no sample or legacy data, no dev
Sandbox - oracle sample data, no dev
Conversion - legacy data, no dev
Dev - "scrambled" legacy data, dev
Config - functional team environment setup
Test - config and dev together, unscrambled user data
Test2 - I have no idea why this here, but it is :)
Training - for training users, selected legacy data and dev
PreProd - everything after test and before prod
Prod
Given that each environment has an app server, a web server, two or more batch servers and a database, I can vouch that a fubarred deployment workflow is hell. You end up with no baseline to tell if your process is bombing due to configuration or code.