Since F-Droid (i.e., the repositories, not the app) builds all apps, a practical solution would be for the repositories (i.e., their signing keys) to be recognized by El Goog. Whether and how much help / obstacle the "maybe we do evil" company puts up for / against this is a different question.
They have to use one key per app, otherwise independent app could end up sharing some permissions (IIRC).
It seems to me this is a blocker to use if google can restrict sideloading like this. Its not going to end with just get people requiring to register their app with an identity. Wont they be able to put presser on f-droid devs to lock out software they consider a threat to some business model?