[SamWhited]

Conversations (on Android) and Gajim (on the desktop) does video chat works quite well in my experience. They have a paid service you can use with it, or it's compatible with any Jabber/XMPP compatible messaging service.