It seems like some continuous deployment strategies could work here, as long as you limit the number of schema changes in flight to a handful.

Customer A is running the new schema, so gets one cluster. Customer Z will get migrated in the next hour, and then none of the old system is running.