We show that the fast moving component of the "bullet cluster" (1E0657-56) can induce potentially resolvable redshift differences between multiply-lensed images of background galaxies. The moving cluster effect can be expressed as the scalar product of the lensing deflection angle with the tangential velocity of the mass components, and it is maximal for clusters colliding in the plane of the sky with velocities boosted by their mutual gravity. The bullet cluster is likely to be the best candidate for the first measurement of this effect due to the large collision velocity and because the lensing deflection and the cluster fields can be calculated in advance. We derive the deflection field using multiply-lensed background galaxies detected with the Hubble Space Telescope. The velocity field is modeled using self-consistent N-body/hydrodynamical simulations constrained by the observed X-ray and gravitational lensing features of this system. We predict that the triply-lensed images of systems "G" and "H" straddling the critical curve of the bullet component will show the largest frequency shifts up to ~0.5 km/sec. This is within the range of the Atacama Large Millimeter/sub-millimeter Array (ALMA) for molecular emission, and is near the resolution limit of the new generation high-throughput optical-IR spectrographs. A detection of this effect measures the tangential motion of the subclusters directly, thereby clarifying the tension with LCDM, which is inferred from gas motion less directly. This method may be extended to smaller redshift differences using the Ly-alpha forest towards QSOs lensed by more typical clusters of galaxies. More generally, the tangential component of the peculiar velocities of clusters derived by our method complements the radial component determined by the kinematic SZ effect, providing a full 3-dimensional description of velocities. ; Comment: 12 pages, 6 Figures and 2 Tables, accepted for publication in the Astrophysical Journal