This is verizon problem, not android. Buy smartphone from retailers who is not affiliated with any cell provider (i.e. without all this junk apps and customized UI), buy SIM card from cell provider, plug it in and use. This is how it works in Europe.
