You could implement the principle of PGP:
Client 1 would be left on the image, Client 2 on the right, and your server inbetween. Since the clients only need to know each other's public keys, your server can take care of exchanging their keys. The only trust issue that could arise is the storage of the private keys: this would be handled by your app. Clients have to be sure that this is handled in a proper way. One way for them to check would be to decompile your app.