If they offer a phone w/ windows mobile and wifi, you could go that route, as 3G data can usually be disabled and you can rely on free wifi. In general the discounted phone prices, at least with ATT, do require a data plan. I'm not as certain about Verizon though. They might let you bring your own Verizon branded CDMA/EVDO phone though. Have you called their customer support yet?
I wanted to buy a verizon cell phone but decided not too once i found out i had to pay atleast 30 bucks a month for the data plan. Even if it has wi-fi. So would i still have to sign up for that damn data plan if i bought a cdma phone off ebay or craigslist for example and activated my phone over the internet? anyway i can get around that stupid data plan?