Algorithm to securely exchange identities
The Simple Protocol:



Alice generates a signature key pair (to sign in step 4, all other signatures in the protocol will be from the original key pairs), calculates its encryption under each of the other participant's public keys, indicates which encryption corresponds to which key, and then signs and posts the result.
The other three participants each decrypt the message encrypted with their public key, calculate the encryption of that under the public keys belonging to the other two of those three participants, indicate which encryption corresponds to which key, and then sign and post the result.
(With signed messages) Those three participants confirm that they got the same signature key pair from all three sources, and then all four participants agree on a time period for step 4.
Each participant generates a new key pair, and posts the public key along with its signature under [the signature key pair from step 1].
Once four posts with a public key and its signature under [the signature key pair from step 1] have appeared, each participant posts a signed confirmation, with the lexicographically sorted list of those four messages, that their public key was the public key in one of those messages.
After each participant has confirmed in step 5 (and made sure the lists of messages match), use the public keys from step 4.




The potential problem is that a participant can trivially force an abort with zero chance of getting

caught. $\:$ Every way I can think of for this loses the property that the [honest participant]-[key pair] relations will be forever hidden from an attacker who doesn't break the cryptosystem before

the protocol ends (long-term security for all participants). $\:$ The best way I can think of is:

(With all messages signed),
Use generic multi-party computation to compute the lexicographically sorted list of a new public key from each party. $\:$ This requires oblivious transfer, and I have no idea how many of them it will need. $\:$ This does not need any anonymous posts, and works against any number of disruptive participants.  Depending on what oblivious transfer protocol is used, this might provide long-term security for one of the participants.