Don't know about GV, but i use PingChat. It's available for android/iphone/blackberry. I used it when i was in south america to chat with family back home in the US. It works on 3G or wifi. Both of you have to install it on your phones.
Not sure how sms works internationally (rates and such), but all of the IM apps should work (google talk, aim, ym, msn, pingchat)
Pingchat will work like BBM with the confirmations. LiveProfile doesn't have the BlackBerry version out yet, but it should be available soon. Most should also work via 3G or wifi.