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.
The fact that ALTER TABLE locks on most databases is not the primary reason changing a schema is hard. The primary reason is that a schema change breaks the application [1].
Migrations are programs, but your existing live application is also a program. Changing the schema breaks your live application to prepare for the new version of the application.
This is true for NoSQL too. If you change the format of your documents you applications might need to be modified to support both the old and the new format at the same time.
MySQL had some historic issues with schema changes -- adding a column to a table with a few million records could take hours. While it does have a lot of work to do -- it is restructuring every page of the database -- in competitive products such a change takes a minute fraction of the time (limited only by IO performance).
Most changes would still block, yes, but at least in PostgreSQL many changes will only block a short time (since they do not require a full table rewrite, only altering the table descirption) and in my experience rewriting a table is generally quick for a decent sized database (tables with a handful of millions of rows).
