Here's my Django Fabfile. With it, you can deploy a new project with just a minute or two of configuration. It's been developed and tested over the course of several real-world projects.
I'd love to not have a Fabfile, but none of the Platform-as-a-Service offerings are there yet. App Engine is too different, DotCloud is too expensive, and I couldn't figure out Gondor (and it's in private beta).
The Right Way to solve this problem would probably include dedicated configuration management tools like Puppet or Chef. I haven't made that leap yet, and this solution Works For Me and allows me as much control as I want. I hope you find it useful.
Setting up a new project involves changing just a few settings, then running fab stage_production bootstrap_everything. Deploying a new version of a project is fab stage_production simple_deploy. Updates and rollbacks happen with atomic symlink swaps. You can run multiple projects on the same server, making this a cost-effective solution.
Finally, here's a video of me launching a new project, start to finish. The first second of the video is a little garbled, but it corrects itself. To actually see what I'm typing, you'll want to watch the HD version.
Link again: django-fabfile.