Any reasonably recent phone will be able to piece together a multi-part text message correctly, even with the messages arriving out of order, etc. It takes a really old phone or a crappy network (that messes with the message format) to break that.
Skype works fine with 3G, even with voice (though only when there is good reception). For chatting, there is an iPhone-friendly web service that's called
s4iphone.com. The problem is you can't stay logged in and have it alert you when new messages come in while the phone is off/sleeping, but it's a start. Skype on the iPhone is bound to happen once the SDK is released, at least for text chat.