Guys, take it from a qualified non Native speaker: this is not such a good idea. Not because of us, but because of them, and by them, I mean the ones holding the pan by the handle -Government, buxiban owners, parents, etc.
I mean, it is nice of you to be so open and PC about it. Yes, in real life, many non Natives of various persuasions and capabilities are actually teaching, mostly illegally, some in a fussy area, others with permits for something else, and a few handful on PARCs and marriage visas. That it happens does not mean it should. Why?
Think about how they treat Natives English speakers, even qualified ones. Think about all the hassles, all the under reporting of salaries, all the non payment of taxes, all the murky things that can happen. Multiply it by “I don’t care” to the n power. If someone steps the conventions -7 nations allowed, TESOL, college degree, any of those- little will they care to give you less hours, underreport, send you to teach kindergarten or in another school, etc. They can set you up and lose you, an expensive qualified Native, just because there are so many. Now imagine that on a non Native English speaker, who in their eyes is in a lesser position.
Just because you look down on the quality of instruction here in Taiwan -and yes, there are many questionable schools and most parents care too much about the white face than other qualifications- that doesn’t mean you should encourage it more. Because it doesn’t matter if the non Native has a PHD in Linguistics. Any school that hires him cares 000.000 about that, just a pretty face, a warm body, an income revenue.
To make matters worse, due to the economic crunch, there has been a change in the market. It used to be people hounded you on the street to teach them. Now, there are way too many unemployed people in et West looking for a quick buck here. And Taiwan is no longer a backpackers, passing through and refuel stop. The OP couple surely can be hired, surely there will be a school more than happy to hire them, but heck if they will get paid any 600 an hour, for starters. And they will be at the mercy of any pissed off teacher/parent and one phone call away from deportation.
It would be nice like in the days of old when people came and taught and got their money and left. But that sadly is no more. Too much at stake now.
As for student regulations, you need the schools approval. For that, it is at least 6 months of very good grades. And then they will ask the million dollar question: why do you need to work? It is not like in the States or Canada where such permits are easier to get.
Complain all you want about the regulations regarding teaching. It is their sandbox, their rules. I do prefer the idea of the OP coming to Taiwan to work on something else, white collar, and even get more money, better conditions, and less hassles.