Build .debs either locally or (preferably) from CI, push them to an apt repository, apt-get install to production from puppet/ansible.

EDIT: I should explain how this actually helps solve the problem. If I'm building a package locally, I can take advantage of all sorts of cached files which I can't assume are present on the production server. I can also use tools I don't want installed in production to speed up the process. Building a local package from cached gems is pretty quick, and will get much quicker once I've got precompiled gems sorted out. I haven't got a particularly good answer to speeding up `rake assets:precompile`, but having it fail locally is better than having it fail in production.

I use fabric, I can type

>> fab push prod deploy

to push changes to my repo service, ssh to production servers, pull down changes via git, and restart necessary services/run associated tasks like symlinking to new static content.

Aside from "deploy" I have tasks to update the virtualenv etc, this has worked well for me for a few years.