Yes it is possible and, in fact I just did it on the phone at Apple Store few days ago when mine was replaced. I had to call Verizon and provide the new MEID (Settings->About->MEID) and "Reprovision Account" (Setting->Reset->Subscriber Services->Reprovision Account). On the old one, you need to Reset Network (Setting->Reset->Reset Network Settings).
When you call Verizon, make sure you have the Data Phone Number (Settings->About->Cellular Data Number) that starts with area code on the old iPad. The whole process only took a few minutes.
Ipad 2 Verizon being so new, the guy at Genius was not really familiar with this transfer of data service so, at first, he could only provide me with Verizon customer service number.
Hope this helps.