I'm going out on a limb a bit but I think this might work. Notice all the disclaimers.
If you have a spare GSM phone, go to an AT&T store with it, buy a pre-paid SIM card, and have them activate it. Go home and swap the card into your 3GS. It should work immediately for voice and text. Data requires some extra steps but it doesn't sound like you care about that. My local store just gave me a SIM and activated it in my phone when I purchased a $10 credit. YMMV.
That said, I have not taken the next step of moving my card into an iPhone. I'm planning on buying an unlocked 4S but I'm working up the courage to pull the trigger on a big purchase that might not work out as expected.
Don't take your iPhone into the AT&T store as they don't support iPhones on prepay plans and "don't support" translates into they won't sell you the SIM.
If you don't have a spare GSM phone, you could buy a cheap, used one on eBay. You could also try buying a cheap AT&T GoPhone ($10 at Best Buy) and using the SIM from it but I've heard that the SIM card gets locked to the phone for 90 days after it's activated. I also hear that you can take the card out before turning the phone on, put it in your iPhone, and activiate it from the AT&T web site.
In theory, "don't support" could translate into actively blocking iPhones on the prepay plan at some point but no sign of it so far and once you get activated, you don't care anyway.
If you do this, let us know how it turns out.