Yeah binary patching would basically solve this issue and wouldn't be any more of a hassle for the user than vanced already was. For a similar example, see the way most alternative Minecraft servers download and patch official binaries on first start (they started doing this due to getting a bunch of DMCA takedowns a few years ago).

With a bit of effort, Vanced could even have the download page perform the patching and signing in JS/wasm, then include the privkey in the app so it could download, patch and sign new copies of itself on the fly.

Or, for better security, have a web service that signs any APK that matches a set of hashes. Clients patch the APK locally, then send it in to get signed - everyone now has byte-identical APKs, but Vanced severs never technically distributed Google's binaries.