The bottom line, and I mean the bottom line, is that the iPhone will come to Verizon eventually. Maybe not the iPhone we know today, maybe an entirely different concept of the iPhone, but Apple will sell a Verizon phone one day.
What's my reasoning? Verizon is huge- even if they were not the largest provider, which they currently are, they represent a major part of the market. Also, Verizon's service is simply better taking in account the entire United States. More people have service in more places, and traveling will not induce the woes of current AT&T traveling. What does that mean?
It means that the iPhone will become more viable for business. Business is a major influence for phone sales, as you all know. With Verizon's superior network, massive user base, comprehensive network coverage, and inclusive (maybe not always "cheap) plans, Apple would be stupid to not make a deal with Verizon, and Verizon would be stupid to not make a deal with Apple.
Apple is a business, and they want to make money. They have made smart decisions so far, as is apparent. Staying with AT&T for years to come is simply not wise and I just cannot see that happening.
My prediction is that Apple will introduce a new phone concept when they go over to Verizon.