The market is very tough at the moment. The supply of teachers is too high, and demand in terms of number of students is falling.
As for how everyone else got a legal job; some sorted out a position with a chain school before they came to Taiwan, while others did what you are doing and walked into schools chancing their arm. It was easier to chance your arm in the past. I was out of Taiwan for a year and came back in May. I knew that it was tough to find work so I made sure that I arrived in time for the summer recruitment window. It still took me until the end of July to secure a full time job which started at the end of August. You are looking for employment at a much worse time of the year.
I can't give you any advice other than to keep on banging away, walking into schools. Eventually you'll walk into a school just when some flakey western teacher has gone back home and you'll land a position.