Ok so Verizon just issued a press released about releasing an iPad bundle with their mifi in 2000 stores on October 28th. While there is no 3G connectivity that could mean we are not to far off for a Verizon iPhone.
Source: Verizon iPad October 28th: Let The Apple & Android Showdown Begin | Android Phone Fans