One solution is to add a datastore entity and if set use that and else use the config version at head.

The way I did it before a bunch of times: 
1. Add ConfigNew structures to _existing_ config, perhaps duplicating old config. AppOld keeps using old configs, ignoring new stuff.
2. Update OldApp to NewApp, so it start reading new config structures (ignoring old ones).
3. Delete old config structures, leaving only the new ones.
4. Cleanup code to not mention old config structures at all.

That seems like a good way to do it when the config change introduces new structures. Although, in some cases, the config may not introduce new structures, but instead different possible values for some fields. (Example: Recently there was a change of a "host" field from "https://<domain>" to "<domain>".)

I agree. That seems like a good way to do it. For the case qyearsley mentions, we did sort of do it that way - it currently accept both values due to some extra code in the App. 

I think I'll force out the new config format with some babysitting this time around, but I'll add a section to the playbook about this for future changes. This becomes more important after dogfooding has started.