I am not sure if such system existed in the past or if I read about it in some sci-fi book, but it worked as follows:

You generated your key pair. In (almost) every country in almost every city there were “key signers” (basically trusted members of the PGP community). You met with them and they verified your identity and signed your public key. You needed to visit couple of them to get enough signatures to obtain certain level of trust in the PGP community. Once your level of trust was high enough you could start signing keys of other people. Too good to be true I guess…..