I've got Skype lite. It only works on wifi. If I understand right, with Verizon you will be able to video chat soon. Verizon and Skype seem to have partnered. I'm on unlocked TMUS. Skype to Skype over wifi works.
There's a few more - Fring, Nimbuzz, Truphone. You can also find a SIP account.
All these will have a charge if you are calling a landline or a mobile on another service.