I’ve never heard of rentals here. Considering how cheap phones are, I don’t know that there’s any market demand for them. You can buy a used phone in any nightmarket for around NT$1200 (US$35) if you just want communications.
The SIM cards are a little harder to get nowadays. I had to go to a dodgy Indonesian food place which sold them without demanding the apparently-now-required two forms of Taiwan-legal ID. You could also pick one up in Snake Alley (I saw a couple of carts selling them there three weeks ago).
FarEasTone’s SIM sells for about NT$600 (US$18) and gave me enough time for a month. After that, they charge more for refill cards (most people keep buying the refill cards because they want to keep the phone number that their SIM is programmed for); my bill was running about NT$300 per week (US$9).