Korea drug tests their foreign workers, you say?
So does Taiwan. ONCE at the beginning. Along with our tests for HIV, Hep B, and tuberculosis. I can't imagine Korea is much different. I can't honestly see Korean authorities going around to all the English conversation schools, stopping teachers mid-lesson, and asking them to pee in a cup.
That said, Japan and Korea are not places you want to be looking for any illegal drugs. The locals LEOs in these two countries are as rabid as those in Singapore about enforcing their drug laws, especially for foreigners.
Taiwan is a good choice, if not for the fact that it's a saturated market. Summers there are brutal.
China's an adventure, and people will BEG you to take English teaching gigs, no joke. But it's a grimy, rough place where not many people speak English, and their currency is insoluble.
For leads worldwide, check out the ESL Cafe (google it), or lonelyplanet.com's Thorn Tree Forums.