If the clients are communicating with the server encrypted, and we assume we can trust the server, one easy way to do it would be for the server to broadcast some cryptographically random chunk of plaintext to all clients (say, 2048 bits).
The clients cryptographically sign the plaintext with their shared secret(s), and send those signatures to the server, which stores the responses in a hash table, where each response also maps to a list of clients.
When multiple clients give the same signature, the server informs all of them, and each client sends an encrypted packet containing its ID along with a timestamp and nonce, encrypted by the shared key. These packets are then sent to each client in the list, along with a temporary client ID generated by the server.
When a client wishes to communicate with another client, it sends that client's temporary (server) ID to the server. When two clients both send each other's temporary ID to the server, the server transparently creates a tunnel between them. From there the two clients may continue to communicate using their shared channel, sending a timestamp and nonce within each encrypted packet.
Pretty sure this is safe from replay attacks (because timestamp and signing random data), but I'm assuming a strong crypto algorithm, a good crypto signing algorithm, and a cryptographically-strong source of entropy for both clients and the server. Even if someone malicious were to connect to the server during the original signing phase, and were somehow able to guess a working signature (or were able to compromise the entropy source quality of the server, which would create additional problems, anyway, but since we're pretending) they wouldn't be able to get past the peer selection stage where clients choose which other clients they want to connect to.
It does create a DoS opportunity for the server, which really ought to be stateless, but OTOH network connections inherently create opportunity for DoS; either you let anyone connect via SSL, and exhaust memory / cycles / bandwidth, or you start rate limiting, and possibly exclude legitimate users.
EDIT: I answered this question as a theory question, rather than actually giving code or an existing algorithm (AFAIK). Since it's a toy problem, anyway (assuming the server can't be hacked is going a bit far), I thought that would be okay. If that wasn't what you were after, I apologize.
