I suppose that's possible, my friends (neither of whom had teaching certificates of any kind or were even native english speakers for that matter) got in two years ago and things can change. And it's not like they take everyone. There are interviews and all that, because an increasing amount of people want to go to Japan, but I never heard anything about making a TESL certificate necessary. Besides there's still Korea, they're always looking for English teachers too.