Getting a promoter for each country should help you a lot - they know the right venues, the contacts etc. - but it is not necessary. I have known people who just went on the road and took what they could find, but you are rarely likely to find the most suitable gigs at that sort of short notice.
If you have your music on iTunes, Amazon or other global sites, you should be able to track where it is most popular - this could help you decide where to tour.
To help venues/promoters verify you, have a range of live footage on YouTube so they can see what you look like, and carry lots of demo CDs to give out.
I don't think there should be much concern about merch (other than making sure it doesn't get stolen) but research what might sell best in a particular region (eg for us, stickers and badges of our cartoon icons would be first on our merch list for Japan)
Language barrier can be a problem, but being able to greet the crowd in their own language will get you off to a good start. In saying that, English is pretty much ubiquitous so should work, at least partially, in most countries.
Alternatively, you can deliberately misuse the language (see the first video link in my profile to see what I mean)
