As a protocol, XMPP (formerly known as Jabber) would fulfill a lot of these requirements (Possibly because WhatsApp is using XMPP on the backend)
It is massively extendible, so I'm picking a specific client that covers a lot of these requirements. Its impossible to cover all since things like being able to pick a contact on your address book is because whatsapp simply uses a phone number as a username.
Other than video and group chat, any jabber client with OTR would do - I'd recommend chatsecure - it does seem to do multi user chat (though not chatrooms) without OTR, and runs on your two target platforms (and you can use pidgin or kopete on the desktop side for OTR conversations).
Its free, can send photos and videos the usual way and does everything but search contacts in address book of the phone.
Video would be covered by jingle, but I can't seem to find a good, well recommended android client outside the old obsolete google talk.