If you want to go somewhere specific, best bet is to come here and look, but you may also find something on places like GaijinPot.com or ELTNews.com, so play the percentages until you have enough money and time to come here and look around. It'll take 1-2 months just to find a job if you come here; depends on your interviewing ability and the time of year.
TEFL certification is not necessary for work here, but I recommend it if you want to make this a long-term venture. Don't take any that is online; get something that is better than a weekend thing, too.