Since there are no viable alternatives, I guess it's time to go back to owning a cheap corporate/government approved phone for official business (i.e. banking), and another one that I actually use.
As an aside, the presentation[0] doesn't really go into the details how they will enforce this (on-device? Remotely? If the latter, can I just remove Play Services from my device to sideload whatever?), but you can apparently submit feedback about the verification process here[1].
[0]: https://goo.gle/play-console-android-developer-verification [1]: https://docs.google.com/forms/d/e/1FAIpQLSdpZbsJCS-f7CtMbZPn...
Depending on your definition of "viable", you might consider GNU/Linux phones.