With the ZVRS Z4 Mobile or Sprint VRS Mobile App, yes, you can use a Samsung Galaxy S Epic 4G on Sprint Wireless, or Samsung Galaxy S Tab on virtually any carrier.
You _can_ run those mobile apps on a Google Nexus One, or an HTC Desire/Incredible (and other Android phones), but there will be no front-facing camera (Android 2.3 introduced the front-facing camera API - older version of Android must work within per-handset manufacturer APIs to access the front-facing camera, and the above apps doe not currently work with any other APIs).
Samsung Galaxy S Tab does come in a Verizon version, that would work for you. The 3G speeds are somewhat wanting. I wouldn't wait for LTE myself, they're at least a year behind the Sprint deployment, and there are virtually no devices or nearly enough coverage to make it worth it yet.
Verizon has a 5GB cap on data access (unlimited doesn't really mean unlimited), so you'll need to make sure you keep within that data plan's limits or your videophone will simply stop working.
If you're looking for a mobile phone form-factor, and you want to stick with Verizon, you may want to wait until LTE devices come out and you get LTE coverage in your area. Barring that, you could get a Droid and a mirror (rear facing camera), and cross your fingers that your data speed will be fast enough. That, or tether with a mifi.
Some people have gotten clever and tether an iTouch off of a Clear Spot 4G, or Sprint Overdrive 3G/4G, or Mifi 3G device. You could, in theory, do that with just about any mobile device that has wifi and that can run a videophone client. The big problem there is battery life (4 hours).
There is a Samsung Tab with wifi only (no carrier 3g), that would tether off of one of those, but your battery life on the mifi/overdrive is really going to be the limiting factor.
Again, you _can_ sometimes get passable 3G data connections, and you can sometimes get really poor 4G data connections, so don't be too confused by the 3G/4G speak. Just know that, generally, if you get a 4G signal on your device, it will usually be fast enough to place a video call, where a 3G signal may not.
There is presently VRS for Facetime on iPhone/iTouch, but you need wifi.
While there presently isn't VRS for Tango, Qik, Fring, or other mobile clients, but that doesn' t mean some enterprising VRS provider won't give that a go eventually.
The easiest path would just be switch plans from Verizon Wireless to a Sprint Wireless Samsung Galaxy S Epic 4G, install the above mobile apps, and be done with it.