This approach would work. You could create a channel for every user pair. You may not need to necessarily store the channel in parse. You could just have a naming convention - something like channel_user1_user2 In addition to standard publish/subscribe, I would also suggest using history api to catch up with chat messages that the user may have missed since the last connection. Also, you can use pubnub presence api to determine if any of the users are online
The android example at https://github.com/pubnub/java/tree/master/android shows how to use publish/subscribe and history