I think the problem is that we already have the networks and protocols to synchronize time (NTP, PTP, etc.), but not for timezone DB data.
But most operating systems already have their own mechanism to update their timezone database. This is not a problem. Shifting timezones by 15 minutes every few thousand years would work with current software.
All we need to do is to agree that UTC will have no more leap seconds.