I don't want to presume that I'm smarter than Craigslist's engineers, but why is this so hard? Schema changes should be captured in migrations, which are programs, and could be coordinated to run in parallel on thousands of machines in a moment with a shell script over SSH.