The solution is pretty clear, simply make it easy to do what the author suggests in their article, in a safe and repeatable way. You define your new schema, and you define the tranformation rules to run on the old data. In turn, the database applies these lazily. There'd be some formality necessary to prove certain operations could be applied lazily to provide a consistent view of the data. People are doing this by hand now; it should be part of the system. One can imagine a mathematical model that involves deferred relational operators. The constraints that would be imposed would probably be that certain operations would not be permissable until others complete. For example, it might be necessary, when running one of these lazy migrations, to "flush" the remaining untransformed rows to the end before you are able to apply another one. The upside is your migration scripts run instantly, becuase they have no side effects until the next transaction.

The CAP theorem I think often gets rolled up into these "NoSQL" discussions erroneously. One can still model data relationally but materialize it in a way that reduces ACID compliance to survive in the face of network partitions. Arguably this is a red herring though. In practice, the "network partition" problem to me seems to be only really worth worrying about if you are Google or Amazon and are running cross-data center data storage. For the majority of the world this is not something that needs to be worried about. (See: VoltDB's choice on the matter.)

Edit: By the way, I'm not saying any of this is easy. It's hard, really hard. (I couldn't do it.) But the point here is that it's easy to get caught up and think these 'new' document databases are solving these problems. They're not. They're putting you back down to the assembly code level and forcing you to do these things yourself. The whole point of the RDBMS is to provide an abstraction layer. They're removing this abstraction layer and heralding it as a step forward. It is, in a bizarre sense similar to how it's a "step forward" for you to be able to access the registers on your CPU, but it's surely a step backwards in many ways as well.