To have a smartphone active on the Verizon network, whether it is prepaid or post paid, you must have a dat plan.
A note to watch...I have an Iphone4 with an unlimited data plan which expires in February. Since they announced the new pay as you go plans, I have been watching the data usage (WIFI vs CELL data) and have found that my Iphone4 does not reliably switch between WIFI and cell data. This didn't matter, and I never checked, until they eliminated the all you can eat plan. I told VZW about it and they switched out the phone as a defective because I had their insurance. The replacement unit does the EXACT same thing. VZW has turned me over to Apple support and they want to wipe the phone and reinstall the ios which I am yet to do with them. I am not hopeful though.
You should consider turning off cell data and leave WIFI on. It will notify you if it cannot access the WIFI and you can then decide if you want to incur the cell data charges and turn it on. You can turn WIFI on and off from the top menu but you have to go three layers in to turn cell data on/off. If the unit is trying to access WIFI and cannot, the pop up window takes you right to the cell data screen.
I am waiting for one of my three phones to end its term and then I will likely go to another carrier with an unlimited plan for all three...too much drama with VZW. I have been with VZW for about ten years and I have come to feel like they just want you to bend over.
i wouldn't bother with reinstalling the OS. this is a known issue with iphones. i mean, you can try it, but like you said, i'm not hopeful.