Convert to a one-time escape hatch unlock via a random-question quiz hosted by Google that assesses security and computing knowledge?
If the intent is to prevent the dumbest users from doing something, then a good place to start would be an assessment to determine if a user is actually dumb or not.
It's oxymoronic to attempt cover-all methods that encompass both (a) advanced users who do want to sideload & (b) people who will type in anything the internet tells them will make a cracked app work.
Then the staff (or a chatbot) could be trained to intervene and confirm that the caller is not getting scammed.
Phone vendors could also be licensed to use a simple web interface to do this at the shop if the buyer requests, and the vendor license would be logged so if the user gets scammed immediately after unlocking it's not anonymous who helped them get scammed.
Similar to Root, really, but mid-tier since enabling Root involves giving up some other security assertions.