1) You don't need a data plan to use GPS on a phone, there are offline options. Look into Sygic. That'll lower your actual data needs drastically.
2) If it's either an iPhone 4 or 4s, you should be able to activate it on either Page Plus or Selectel. I'm more likely to recommend Selectel over Page Plus these days as Selectel is approaching longer term stability and Page Plus is about to complete its final conversion into another crappy America Movil MVNO like StraightTalk, NET10 or Tracfone come January once the domestic call center is closed. If it's a 4s, be sure to get Verizon to unlock the SIM slot for "global GSM providers" before you leave.
3) Full factory reset as Dean recommended, though the reality is that there's no safe way to completely wipe your data on a phone. Someone determined enough could recover data even from a wiped phone. Don't be paranoid, just recognize the issue for what it is. This is partially why I don't use a smartphone for these sorts of things.
By other threads, I trust you're including
the guide with that. The thing that hangs people up is the illusion of overwhelming market diversity. The reality is, if you know what network you need (you already stated you have a Verizon phone) and what sort of usage habits you need, you just select the MVNO on your desired network offering the best price for the usage patterns you have. Part of the purpose of the guide is that I've already narrowed the field down to a best of breed... it's just price picking at that point between the MVNOs on the network you're planning to use.