Understanding the origin of fast radio bursts (FRBs) is a central unsolved problem in astrophysics that is severely hampered by their poorly determined distance scale. Determining the redshift distribution of FRBs appears to require arcsecond angular resolution, in order to associate FRBs with host galaxies. In this paper, we forecast prospects for determining the redshift distribution without host galaxy associations, by cross-correlating FRBs with a galaxy catalog such as the SDSS photometric sample. The forecasts are extremely promising: a survey such as CHIME/FRB that measures catalogs of $sim 10^3$ FRBs with few-arcminute angular resolution can place strong constraints on the FRB redshift distribution, by measuring the cross-correlation as a function of galaxy redshift $z$ and FRB dispersion measure $D$. In addition, propagation effects from free electron inhomogeneities modulate the observed FRB number density, either by shifting FRBs between dispersion measure (DM) bins or through DM-dependent selection effects. We show that these propagation effects, coupled with the spatial clustering between galaxies and free electrons, can produce FRB-galaxy correlations which are comparable to the intrinsic clustering signal. Such effects can be disentangled based on their angular and $(z, D)$ dependence, providing an opportunity to study not only FRBs but the clustering of free electrons.