There are plenty of instant messaging applications on Android. Many merge a bunch of instant messaging services, like Messenger, AIM, Skype, Facebook, etc., for extra convenience. All Android devices are fully capable of operating without a contract or a SIM card, though you'll be receiving notifications of that when you boot up. Wi-fi connectivity is a standard for smartphones today.
As for recommended choices, it really depends on your budget, and your location. You're in Canada, so if you buy straight from the carriers, there's a bit of a limit to the range of devices. Rogers Wireless recently came out with their Xperia Arc (my current phone, love it), and Xperia Play. Both are fantastic devices, and run the latest software (Android 2.3 Gingerbread). The Xperia Play has a nice bonus of seconding as a PSP, if you're into that kind of stuff. Telus gives you some options with the HTC Desire HD (though the battery life is iffy), as well as the popular Samsung Galaxy S series. Bell has a good range of phones, including the dual-core processor Motorola Atrix. Another option could be the HTC Incredible S. All major carriers carry the Google Nexus S, which runs the stock Android operating system, and is quite snappy. Most of these phones without contracts will cost you $500 or more. There are some more 'budget' phones out there, like the Acer Liquid E or HTC Wildfire S, but honestly, I don't think they're worth it.
Looking outside the major carriers and onto the online retailers, you get a much better variety. Samsung's recently released Samsung Galaxy S II is extremely popular, though runs at over $700 without taxes. HTC came out with their HTC Sensation dual-core phone just a couple of days ago, and it costs significantly less for a similar experience.
Originality said:
The latest version of Android is 3.1, which to my knowledge is only available on the ASUS Eee Pad Transformer. The latest version for smartphones is 2.3 (gingerbread). If the phone is fully routable, you can just install a custom ROM for it, such as the latest version of CyanogenMod. Don't worry so much on what version of android it has, just the specs it has.
Clarifying a few things. The latest version of Android for tablets is 3.1 Honeycomb, and it is available for devices like the Motorola Xoom already. All new smartphones should be running 2.3 Gingerbread, so there isn't a need to worry unless you're picking up an old device. Even so, they should be running 2.2 Froyo, and nothing before that.
Rooting (not routing) is kind of like a jailbreak, though more complex in a way. It gives you, basically, Administrator access to your phone, letting you flash ROMs, run advanced tasks, and even operate certain Linux codes.
