Qualifications for foreign language teachers are covered in Art. 40 to 42 here:
Art. 42 refers to buxibans (so-called "cram schools" or "supplementary schools"). The other types of educational institution are listed in Art. 46 Par. 1 Subpar. 3 of the Employment Service Act.
I've never really scrutinized the qualification standards for non-buxiban teachers, so maybe I didn't notice a loophole in there.
Note that the passport requirement is all about citizenship, not the actual language situation, so for example a Canadian citizen who meets the other criteria is automatically qualified to teach both English and French.