They would probably have to through a similar procedure as they do to get a replacement social security card. That is, they would have to present at least a drivers license and US passport at one of the local social security administration offices.

At that point, they can regenerate the key-pair and have the SSA official sign the public key and keep that on file.

Now, presumably, it is possible to forge both documents, but I would think that the government could check their records (federal and state) to verify the authenticity of the provided documentation.

Exactly. You can't have perfect trust in every citizen to keep track of these things. And if it's a government issued ID in the first place, I see no trouble with them having your private key as well. Just don't reuse that key.

This would take a lot of solid investment politically, and technically, to make it even slightly feasible to work for the average Joe.