NOTE: This is not specific for Taiwan! Tons of it is built on heresay and my own research regarding work for next year.
From what I've seen, a TEFL degree is the bare minimum you need to apply to many jobs, as well as a 4 year uni degree. If you have a degree in English or Education it may be different.
Some jobs don't ask, but usually these have something hairy beneath the surface.
I don't know the specifics of Taiwan, but looking at most programs/jobs they want some form of teaching degree.
Of the ESL degrees, CELTA is a great starter degree and many schools seem to have a good impression of it. It's a pretty hard program though - 4 weeks of TEFL bootcamp.
Hess seems to be the best of a bad lot, but seems to be tolerable if you work for them with the intention of finding something better and don't borrow money from them.
OP - what you seem to be looking for though is a door into the East. What are you feelings regarding Japan? Give the JET program a look - good salaries, incredibly safe and will give you teaching and Asia experience. You are also subsidized when taking TEFT courses while on the program (and you workload is somewhere between 'bugger' and 'all').
My problem is that I don't have enough money to go without having a job lined up. My loans are already in repayment, and even more of them will enter repayment as soon as I graduate. So, I have to move with money that I can save while in school (read: enough money for a one-way ticket and set-up expenses), and quickly have a job that pays the bills (50,000NTD would be acceptable, 60,000NTD would be luxury).
Again, take my advice with a grain of salt - but I've had friends try various places (Middle East, Thailand, Japan) coming over solo and those without the financial fat to survive for a month or two have fallen flat on their faces. Some jobs offer a loan, but in many cases this can be used to leverage you to work for them for longer.
Two words: JET Program. Do it. I know it's not Taiwan, but it's not far and you can head there after you've saved some cash. And earning $2K US a month basically tax free is just awesome for anyone with loans.