Both Taipei and Kaohsiung cities have launched high-tech bicycle rental systems, and Tainan is talking about it. I haven't used any of these systems, but I looked at one of the rental points in Kaohsiung (pictured left), right outside a KMRT station. Even though the English version of the instructions was perfect, it still seems a little complicated. Moreover, the bicycles are definitely on the small side if you're a Western man of average dimensions.
On Kaohsiung's Qijin Island there are a number of private bike-rental businesses. Qijin has some quite decent bike trails, and the traffic isn't too bad.