Even WinAuth (which is probably the most potent third-party authenticator app) says it's really designed as a backup to using a phone. I'd be really hesitant to trust anything third-party without official first-party support, though that's not based on any bad experiences. Just my own paranoia at the idea of being locked out of something. I use Google Authentication as well as Battle.net's official clients on my phone.
As for the idea of getting an Android phone, look at T-Mobile's month-to-month. If the coverage is good in your area, then jump on it. The price is great. My issue is that since I don't live in a top-100 metropolitan market (I'm in a top-200 market but not actually in that city), I had spotty data coverage. GPRS-only in a town of 15k 5 miles from here, occasionally spotty coverage in my home town of 35k (which also includes kind of bad reception at my house but maybe the aluminum siding is a contributing factor). If it works for you, the price can't be beat, and then that means you should get a Nexus 5 from Google Play since it supports T-Mobile's LTE and HSPA+ bands. Or if you want to save some more money, maybe look into a Moto G, which doesn't support LTE but it's only $200 for a 16GB version and will get KitKat in January.
I do not understand what I do. For what I want to do, I do not do. But what I hate, I do.