We explore the effects of incorporating redshift uncertainty into measurements of galaxy clustering and cross-correlations of galaxy positions and cosmic microwave background (CMB) lensing maps. We use a simple Gaussian model for a redshift distribution in a redshift bin with two parameters: the mean, $z_0$, and the width, $sigma_z$. We vary these parameters, as well as a galaxy bias parameter, $b_{text{g}}$, and a matter fluctuations parameter, $sigma_8$, for each redshift bin, as well as the parameter $Omega_{text{m}}$, in a Fisher analysis across 12 redshift bins from $z=0-7$. We find that incorporating redshift uncertainties degrades constraints on $sigma_8(z)$ in the Large Synoptic Survey Telescope (LSST)/CMB-S4 era by about a factor of 10 compared to the case of perfect redshift knowledge. In our fiducial analysis of LSST/CMB-S4 including redshift uncertainties, we project constraints on $sigma_8(z)$ for $z<3$ of less than $5 %$. Galaxy imaging surveys are expected to have priors on redshift parameters from photometric redshift algorithms and other methods. When adding priors with the expected precision for LSST redshift algorithms, the constraints on $sigma_8(z)$ can be improved by a factor of 2-3 compared to the case of no prior information. We also find that `self-calibrated constraints on the redshift parameters from just the autocorrelation and cross-correlation measurements (with no prior information) are competitive with photometric redshift techniques. In the LSST/CMB-S4 era, we find uncertainty on the redshift parameters ($z_0,sigma_z$) to be below 0.004(1+z) at $z<1$. For all parameters, constraints improve significantly if smaller scales can be used. We also project constraints for nearer term survey combinations, Dark Energy Survey (DES)/SPT-SZ, DES/SPT-3G, and LSST/SPT-3G, and analyze how our constraints depend on a variety of parameter and model choices.