On your phone, buy a phone, Ebay, Amazon, Walmart, Google, T-mobile, anywhere, if you must just get an AT&T Paygo phone, then go to the AT&T store (or call) and say you need a sim card for your account, if they ask why say it was damaged, I doubt they will even ask. Setup the phone, slip in the sim card, done, no new account, no new contract, at worst you pay $10 for a new sim card. Your phone is not locked to the plan, even if you're still paying on it it changes nothing. I've done this multiple times on multiple carriers, including AT&T.
Seriously, it's not that difficult.