At Verkkokauppa.com we deploy several times a day. Our team is fortunate enough to work on our own system, so for small features or bug fixes the turnaround can be as little as minutes.
For us the most important tool is Git. We have a logging mechanism in our deployments scripts whish logs who deployed which version of the code base (SHA1 hash) and when. If we do manage to break something we simply immediately return to the last known good version by checking it out and deploying it. Then we have a lockout policy that prevents futher deployment until the bug is fixed.
On rare occations we have had to do reverts, but only a couple of times over the course of several years.
Other valuable assets that keep us agile deployment-wise is having the whole team physically in one place, and most of our stakeholders in the same building. We also use Jabber internally to make it even easier to communicate on those occations when face-to-face is not possible.
We also use Scrum, but this is a rather recent development, and we did mange the same deployment policy before we switched to Scrum. A continuous integration environment is in use, and does help keep things in order. But for minor features and tweaks with few stakeholders it's not entierly uncommon to simply deploy and communicate with the users directly to check if everything works as expected.
The fact that there is one installation of the system is a major asset. We really never have to deal with versioning. The current version is simply the HEAD commit on the master branch.