In Japan, being a "native speaker" is required to obtain Instructor status, which is necessary to teach foreign languages in elementary, junior high and high schools. Technically, what is required is that you have received at least 12 years of education entirely in the language you want to teach (and not just language classes).
No such requirement exists for teaching at any other place (yes, including universities). Of course, this is only the requirements set by immigration, employers may and do set additional requirements to hire you. The only non-native English speaker I know who is teaching English in Japan has several English teaching certifications, and is teaching at a preschool, which is probably not for everyone.
There are many websites such as GaijinPot where job ads aimed at foreigners are listed, with most of them unsurprisingly being for English teaching, so you can have a look to see what employers normally demand.