That path seems the best, have to buy another phone but worth it to get out of this
The termination fee is prorated too, usually subtracting by around $10 or $20 per month from the original amount - just so the carriers can recover the subsidized pricing on the phones.
The phone itself is locked to AT&T if you didn't know that, so you would indeed have to buy another phone if you were planning to switch to Verizon.
Yes, you could sell it on Craigslist or eBay. Be wary of chargeback scams on eBay. I'd demand a money order or regular cash for Craigslist dealings.
You don't necessarily have to get a brand new iPhone 4S with Verizon, too. You could consider getting an iPhone 4 at a lower price if the money is tight.
Don't forget to talk with customer service too at Verizon. I'd suggest either doing it both online AND in an official Verizon retail store. Mention to them that you want to switch to Verizon but they are going to hit you with a big termination fee. They may give you some credit for your first month of service. Keyword: MAY.
My mother and father in law actually switched from Verizon to Sprint, and at the time they combined about 3 promotions. Sprint actually owed THEM money for switching! They had free activation ($36 per line), free LG Optimus S (I think these are like $200 per phone now with contract), and $100 per line that you port over for new service!
So, they didn't have to pay anything to Sprint for their first few months except for the initial bill - Sprint doesn't apply your credits until you're outside of your money-back guarantee return period, so you're locked in as a customer.
Still, not a bad deal. I'd call Customer Service on the Verizon end and see what they have to say. Worst thing they can say is no.
And also, if you're not happy with service, call AT&T support. I've found them to be quite helpful and maybe they'll even give you some credit if you mention that you may cancel your service and port to Verizon despite any termination fee.