>>1
The server couldn't route chat input to other users if they didn't specify who they were talking to, so instead all chats would go to a central pile of messages that all users have access to. Upon connecting, the user submits a public key and user id to the server, which is made available to all other users. If user A wants to initiate a chat session with user B, user A creates the tuple, (start_token, user_A_id, message_data, user_A_signature), and encrypts it with user B's public key. User B gets the list of new messages, and attempts to decrypt all of them using B's private key. If any of them have a valid start_token at the beginning, the message content and user A's id are processed, an the signature is verified.
It could work if start_token was a content, but that might enable replay attacks. You could make start_token dependant on a timestamp. The cipher would need to resist known plain text attacks.
Oh, this doesn't work since the server can encrypt the start_token with each user's public key and see who is getting messages by tracking the headers of the encrypted messages. The server can tell who sent a message by keeping track of the user's ip addresses and noting which ip the message arrived on. Users would need to either all use the same proxy (which just gives the proxy this information, who can then conspire with the chat server) or an anonymity network.
tldr don't use a central server