It is relatively easy to get work as an ESL/EFL Teacher in all 3 of the countries you have mentioned even if you don't have a TESOL certificate. However, there are a few tips I have for you.
Firstly, be very careful about taking the first job you get offered in South Korea (if indeed you do). The reason is that the country is rapidly gaining a reputation as being one where teachers of English get exploited. I have also heard some horror stories from people who have gained work as teachers of English in state run institutions that are in China.
I would, if I was in your position, try getting work with one of the language school chains. In some countries these chains have 2 or 3 or more schools that are looking for teachers. I would also try getting the work before you leave, as you would require a work visa. Most contracts, by the way, are year long ones.
Just one last thing,
I know a fellow who goes every year to teach English in South Korea. Would you like either me to get him to contact you or his contact details?