First, for voice, pretty much any modern GSM-capable phone will work anywhere except Japan and South Korea (both of which have largely decommissioned their old GSM networks in favor of UMTS even for voice) -- there are basically only four 2G bands in use (850, 900, 1800, 1900) and basically all modern phones support all of them.

For data, ideally, what you want is a pentaband UMTS phone (850/900/1700/1900/2100) -- this will work almost anywhere you can get a SIM card, and is as close to a world phone as you can get. The first pentaband UMTS phone with LTE that comes to mind is the Nexus 5 but I believe there are some others -- looking up other points here, it looks like at least one international model of the Galaxy S5 has both pentaband UMTS and LTE ( SM-G900M )

Unfortunately, no model of the Note II or Note 3 is pentaband, and neither of the US GSM models (AT&T or T-Mobile) has a terribly good set of bands for what you're looking for.

--
Notes by country:

You can't get a local SIM in Japan unless you have a local well enough to buy it for you under his/her ID. They use a mix of bands depending on carrier, but your best bet would be softbank which uses some 900mhz and 2100mhz (as well as a 1500mhz band not used by anyone else.)

Singapore and Malaysia use a mix of 900mhz and 2100mhz UMTS. I don't know if there's much LTE if any there.

Germany uses 2100mhz UMTS (as does Most of Europe with some 900mhz as well.) I assume there's been some move to LTE there now, but I don't know which bands are used. There aren't yet any "world" LTE phones, and I wouldn't worry about it.

--
On specific phones,
Note II
* The original international, non-LTE Note II (GT-N7100), if you can still find one, is quad-band UMTS (850/900/1900/2100) and will work almost everywhere except on some parts of T-Mobile in the USA and on some Canadian networks -- it lacks the AWS (1700/2100) band which those need. It also has no LTE.
* None of the North American Note II models have the 900mhz band. The AT&T and T-Mobile ones have all the other bands you'd care about, and differ only in the AWS band (which T-Mobile enables, AT&T disables)
* Verizon's Note II has the worst international bands; not even 2100.
* Sprint's Note II has an embedded SIM with no slot, and is useless for international travel if you don't plan to roam.
Model-by-model comparison here: http://en.wikipedia.org/wiki/Samsung_Galaxy_Note_II

Note 3
* The international models, which should be readily available (N9005, N9002, N9006) are quad-band UMTS (850 / 900 / 1900 / 2100) and will work on most networks worldwide, except for T-Mobile in the US and other AWS networks.
* The US GSM models from T-Mobile and AT&T drop 900mhz UMTS support (and in the case of T-Mobile, picks up 1700mhz AWS) just like on the Note II.
* The Verizon Note 3s are quad-band, like the international ones - they lack 1700mhz, but that's unlikely to be an issue near home. http://developer.verizon.com/content...xy_note_3.html
* Sprint's Note 3 reports 1900mhz/2100mhz only, which is terrible. I haven't personally checked a Sprint Note 3 (unlike the Note 2 which was one of the reasons I left Sprint) but reports online say that Sprint gave up on the embedded SIM.

So between the Note 2 and Note 3, the Verizon Note 3 seems the best bet for international use if you're willing to use Verizon as your US carrier and can get them to unlock it or find a third party service to do it.

Galaxy S5
* There is a pentaband international model (with LTE, too) -- the SM-G900M -- not sure where you can get one, but if you prefer Samsung to the Note 5, this would probably be your best choice. Google suggests it's a European model for Vodaphone.
* AT&T and T-Mobile - same as Note 2, no 900mhz band.
* There's a Google Play Edition expected, which would be factory unlocked (and the S4 is available now) If it's like the current S4 and other Google Play Edition phones, it'll be based on the AT&T/T-Mobile version with no 900mhz support.

---

Personally, if it were me, I'd just get a Nexus 5 to travel with (or a Moto G, if budget was a big factor.)