What are the risks of in-person private currency exchanging for travellers?
I think that "personal safety risks" are outside the scope of this website, so I'll mention the technical risk - double spend. If you don't wait for one confirmation, a double spent attack can be performed, and you won't get your Bitcoins.

Luckily, you'll only have to wait five ten minutes on average for a block to be found (blocks are one every ten minutes, so the expected delay until the next block is five minutes).

After one confirmation, it's very unlikely such a small transaction will be double spent. If you want to increase your security, wait another block or two.

Traveller A doesn't need to have internet, he can use a Pimpcoin-like card (link NSFW), with SMS notifications of incoming transactions.