[RamDragon]

Well, unfortunately I'm not in Australia, New Zealand or Canada so that helps me very little. Although I do now have a new search term. It looks like TESOL (Teachers of English to Speakers of Other Languages) is a fairly world-wide recognized certification company. I may get certified after I finish my degree.

You should be made aware that Japan makes it very difficult to get a work visa without a Bachelors or Masters degree. You might want to consider earning a teaching degree first then going. If you are confident in the language, you might think about attending school there, as well. I don't know how hard it is for foreign students to go to school in Japan, though.