Ask HN: What does the ideal deployment process look like for this scenario?

Our team of two developers has taken on a new project: updating a slightly rusty PHP 4.x/MySQL 4.x e-commerce solution with a stable but small (< 50) customer base. The lead developer left recently, we have just jumped on board to modernize the project, which suffers from age - it's entirely procedural, not even one AJAX call, ugly UI, some huge tables, barely any caching and scattered ugly joins etc. But it suffers from no major architectural defects and generally works very well. We've been able to successfully integrate it with outside APIs.

The project is going to be worked on by three programmers. The storefronts, UI elements and templates are to be worked on by two web designers. We two developers are currently on-site, and the third is off-site (in a foreign country). We've been working for a while, but the off-site person rolls on next week. The designers have also just begun working on new storefronts.

The old dev server got kind of crusty - it had fallen out of sync with the live, and some functionality was lacking. For example, it was previously impossible to host development storefronts locally. In-house we took the trouble to set up a fresh dev server with dev storefronts and local DNS. Finally, we don't really have any testing yet, although of course we plan to introduce some in the medium term (2-3 months).

After a few weeks of work on this project we're about to jump into the plumbing, i.e. update versions of PHP and MySQL, optimize queries and perhaps add a class structure (Previously we were polishing the UI and performing minor optimizations and API integration).

Suddenly the quality of our dev setup and live deployment process has become very important. There are a decent number of businesses that depend entirely on our product for inventory and e-commerce. Unscheduled downtime of more than a couple minutes is unacceptable any time. We accidentally took down the live server for 15 minutes one afternoon last week and were deluged with phone calls from business owners.

Currently we've not yet installed version control. Typically this is the time to introduce Subversion, or perhaps even Mercurial (used it before, a good improvement over SVN but interface was clumsy and merging seemed to be a kludge still) or Git.

I invite HN commentors (commentators?) to advise us on what a decent development setup and deployment process is in this scenario. Nothing too complex or rigid obviously. For the moment it can remain a little sloppy. It's too early to tighten it up into something formal. We need to transition into it.

Also, intellectually I prefer DVCS, but is it overkill for this scenario? Especially given that the off-site person may have no exposure to the concept, and that it will take a while for our web designers to get it as well. We can after all, introduce it in the future with minimum hassle. We're working at a pretty brisk pace, I don't really want to slow everybody down at this time by introducing a confusing, command line VCS. Also, in our office we have a couple PCs, a couple Macs and a couple linux boxen. Everybody works across platforms. How do we put a system in place that gives us freedom to develop quickly, can ensure a reasonable (say weekly) sync with the live server on a regular basis, and at the same time maintain easily deployable backups?

Free thinking is welcome, but experience in similar situations is what I'm looking for. Useful links from YC (I searched on searchYC first) or anywhere on the internet are also welcome. I look forward to reading your opinions.

PS We have budget and so will definitely at least consider proprietary systems or managed VCS if they come well recommended and reasonably priced.