Do you only have a single instance of the binary running across the whole org? And during deployment to you stop the running instance before starting the new one?
Any change that won't cross deployable binary boundaries (think docker container) can be made atomically without care about subsequent deployment schedules. So this doesn't work for DB changes or client/server API changes as mentioned by OP, but does work for changes to shared libraries that get packaged into the deployment artifacts. For example, changing the interface in an internal shared library, or updating the version of a shared external library.
Seems like a common misconception to me that people seem to believe that you can never change an interface. You actually can as long as it is not published to be used outside of your repositories.
