Page Plus is a popular Verizon MVNO if you don't consume a lot of data. They're known to activate Verizon-locked iPhones on their network if you get the right CSR on the phone.

It's too bad the iPhone 4S doesn't support T-Mobile USA's AWS 3G bands. Otherwise, the upcoming Walmart/T-Mobile plan would be really attractive for this device. $30/month for 5GB of 3G data, unlimited text, and 100 minutes of voice would be ideal for me.