The solution, at least for something decentralized, seems to be a web of trust established by multiple other identities signing your public key with some assumption of assurance that they have a reasonable belief that your actual identity is in fact represented by that public key.

That's what PGP/GPG people seem to do, anyway.

Why can't I get my personally-generated cert signed by X other people who vouch for its authenticity?