I've been thinking about a decentralized way to create an anonymous
identity

This is the fidelity bond/anonymous passport idea that has been kicked around in the forums quite a few times. I mentioned it on the tor-talk once as a solution to the problem that you cannot create Google accounts via Tor without a phone number. It's a good idea but not new. I have encouraged people to implement a server that does it and then some integration for MediaWiki, Wordpress or phpBB, as they're both quite common software that gets a lot of spam and abuse. For instance we could use it on our own wiki instead of paying the wiki operator (does anyone know what happens to those funds by the way?).

You don't need GPG or anything like that - the transactions that spend to fees also contain pubkeys in the inputs, which you own the private keys for. So you can sign a challenge nonce from the server to prove ownership of the "passport"/fidelity bond.