Ricochet[1] works really well. It uses Tor hidden services to communicate. Your Ricochet ID is your onion address. To add a contact, you input their Ricochet ID and a short message, and Ricochet connects to their onion address and sends a contact request. If the contact request is accepted then you'll each show up as a contact on each other's client and can chat whenever you want.
Tor is really perfect for this, you can't get more private or censorship-resistant than Tor.
The UI is currently not great, but that's not a protocol problem.
The biggest problem with Ricochet is that hardly anyone is using it.
Private secure conversations: yes.
Easily available: yes.
Obvious: sadly not, for most people :(.
