Technically you can use IMigrationStep in Commerce, with some caveats (it's not officially public APIs, and it is not built to address multiple instances scenario) 

I came across that, but it seems like something which is not fully automatic, the administrator have to start it. Or is it possible to make it automatic, without user interaction?

It is. You can add AutoMigrateEPiServer appSettings (and value = true of course) and the migration process will be started automatically.

Sounds like a good idea! One problem is still how can I ensure that it (or my custom infrastructure) is not getting run parallel on multiple instances, how can I do some kind of synchronisation across instances in code? (the point is not to trust administrators to start only one instance after deployment)

That part is actually tricky and not builtin. You can do some custom cross-instance lock, like checking if a special value is added to a table yet, if not, add it, otherwise just wait until it is changed to complete, for example 

Ok, thanks for your answer and the ideas!

Commerce team will be looking into that as well (they are already aware it's a possible improvement), so in a future release - hopefully, you can remove the custom lock. But that'll take some time :)