Over the weekend 9to5Mac claimed that a tipster had informed them that Apple could announce a deal with Verizon to carry the iPhone as early as Macworld 2009. The article states that an exclusive agreement between AT&T and Apple were "falsely reported rumors".
During the iPhone launch at Macworld 2007 AT&T's Stan Sigman announced that the iPhone was exclusive to AT&T for a "multi-year" contract. Ever since then it has been speculated on exactly how long the contract is but a recent report from USA Today suggests that Apple and AT&T's agreement could end in 2010.
It seems unlikely at this stage that Verizon will be receiving the iPhone until at least 2010.