> I have yet to encounter any real solution to this problem that allows someone to prove they are who they say they are
I think the solution is third-party attestation.
The government can offer an identity service - it doesn't need to be linked to your real-person, but could simply require proof of residency (by say, mailing you a postcard that you would bring in), but once established, you could use this service to attest your identity to third-parties.
There are companies that increasingly offer this service (like Facebook, Google, Amazon, and Apple) but I think they struggle to avoid conflicts-of-interest in offering this service, so they make me nervous how popular they are becoming in the US and UK.
Where I live, the government provides a smartcard which you can use with government websites and a few non-government sites, and this is used as a second-factor for making critical changes. If I lose this smartcard, I have to go into a government office with some documentation to start the process of getting a new one (where it will be mailed to me, and I can bring it in with documentation to be activated).
I don't find this onerous; I don't have to use the smartcard to do any "normal" things -- the non-government sites (and some of the government sites) allow me to log in using just a password and a mobile-app, but if I were to lose my phone (or my password), I know I have a government-provided recovery mechanism.
Finally, anticipating a particular antagonist of this idea: As far as I know, the government doesn't actually know what services I use this smartcard with (unless the company shares this information, but we already know Facebook and Google and probably Amazon and Apple do) and I have multiple cards with different identifying details on them, so I think any privacy risk is minimal.