Well, actually, I know several foreign teachers in universities in Taiwan. Because of the over-abundance of Taiwanese with PHDs from abroad, it's getting a bit less common, but there is still room for qualified people to teach in universities in Taiwan.
At the moment, the trend is toward people with PHDs in related areas: TEFL, Linguistics, Literature, etc. But there are some universities that hire Lecturers with MA degrees. You will have to go to each university website and try to find an address for the Foreign Language department, or for the English Language Center of the university, and then make direct contact yourself.
Many universities are offering "contract" teacher positions, which means you are not part of the official faculty, and the hours are different. Sometimes there are limits on how many times you can renew this contract. I'm not sure how it works, but I know people who have done this and have their Alien Resident Visa based on that job.
Keep in mind that the Ministry of Education is a bit strict about where your PHD or MA diploma comes from. It's possible to get a fake degree past many cram schools, but the universities are held to a higher standard (I'm not sure if that's really explains what I mean, but you get the point).
So start your internet search and try to get some contacts with schools here in Taiwan.
By the way, I would just like to add that your marital status with or without a local person has nothing to do with getting a job in a university. That's ridiculous.