The service provider(Carrier) should be able to provide it given that they do have BIS system up and running. Now days, I don't think even you can find a carrier that do not have BIS even in a third world country. Call them and ask them to change your plan.
It should be possible, but, depending on Vodafone's network frequencies, he'll most likely only get 2G speeds.
If it's locked to Verizon, the 1st thing he'll need to do is get it unlocked. Then he should just be able to insert his SIM (as noted above, he'll need to have a BIS plan with the carrier).