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.
Afaik Verizon can only unlock the phone completely and not block certain carriers.
Until the iPhone 5, there was no model that supports CDMA and GSM.
The reason your phone doesn't work on an AT&T network (or most international networks for that matter) is because AT&T doesn't run a CDMA network.
http://support.apple.com/kb/ht3939
Best Answer
If the phone is carrier locked, your best bet is to establish service with Verizon and get it unlocked. It's probably unlocked though so you might have luck putting any carrier's valid SIM into the phone. The SIM doesn't necessarily even need to be active - just that it once was valid and used.
Basically a Verizon sim will get you past the screen, possibly others as well initially.