Wow, that sounds like a lot of fun! While you can't touch type on any PDA or PDA phone, it is easier on the Advantage thanks to its larger keyboard. And the larger VGA display means you can see more of what you're typing.
Given the travel locations, you need GSM, so that narrows it down a bit. If you wanted to go the Bluetooth keyboard route, using the Think Outside Bluetooth kebyoard (reviewed on our site) which is still the most popular, the E-TEN X500+ might be a good choice. It also has a VGA display, phone and a GPS which could be handy when traveling. http://www.mobiletechreview.com/phones/Glofiish-X500-plus.htm . It sells for $550 or so.