I think an unlocked S3 would be a great choice.
You will need a new SIM for each country you are going to if you are not going to have an expensive international roaming plan.
The advantage to the S3 is that at 3G speeds it has all four frequencies (850/900/1900/2100 MHz) and I believe that should work in all countries you will be going to. You should check with the carriers that you are likely to use locally to see what their data frequencies are.
Not sure about the frequencies on the S3 for faster than 4G.