You only want to teach in Taipei? If so, you won’t be saving much money if at all on a beginners’ salary, given the capital’s high costs everywhere. Maybe consider Taichung, Tainan, or Kaohsiung.
Most if not all hotels will allow you to leave your luggage there for a few days. Obviously, you don’t leave any valuables. You’ll even see some of them with a special room where the suitcases are with owners names on them. Shouldn’t be an issue.
Cheapest way to travel between cities is either by bus (you can easily find city-to-city buses near any city’s train station) or by TRA. HSR is not what you want to take to save money.
Affordable hotels in Tainan or Taipei? Some others may chime in, but I’m guessing you can even find prices yourself via Internet.
Tainan is AAA baseball. Taipei is the show. Use Google earth to find where the Elementary and Jr. High schools are. Take a taxi or walk to those areas after 15:30 any weekday. Most cram schools are around those schools. Go door to door handing out your resume and showing your face. Don’t sign anything until you’ve done a week of this. After 21:30, hang around the 7/11 or FamilyMarts in those areas. Don’t be seen drinking beer there, yet. Your face is your resume. The area cram school foreigners will be stopping by to pick up their after work medicine. They likely won’t talk to you, but you can try. Invaluable information can be gained by plying foreigners with beer.
Get yourself comfortable with some kind of fun vocabulary game that you can insert into any situation/school. You might be asked to do a demo class on the spot. Happy kids in boring classrooms are your goal. Don’t do demos as they are illegal .
The risk to you is that you won’t have a work permit yet. That risk, however, is extremely small. You should expect that the school will ask you to do a demo. If you aren’t comfortable giving one then I think it will make things difficult for you during your job search. I would say, don’t let them record it.