  In the first paper of this series, we proposed a novel method to probe
large-scale intergalactic magnetic fields during the cosmic Dark Ages, using
21-cm tomography. This method relies on the effect of spin alignment of
hydrogen atoms in a cosmological setting, and on the effect of magnetic
precession of the atoms on the statistics of the 21-cm brightness-temperature
fluctuations. In this paper, we forecast the sensitivity of future tomographic
surveys to detecting magnetic fields using this method. For this purpose, we
develop a minimum-variance estimator formalism to capture the characteristic
anisotropy signal using the two-point statistics of the brightness-temperature
fluctuations. We find that, depending on the reionization history, and subject
to the control of systematics from foreground subtraction, an array of dipole
antennas in a compact-grid configuration with a collecting area slightly
exceeding one square kilometer can achieve a $1\sigma$ detection of
$\sim$$10^{-21}$ Gauss comoving (scaled to present-day value) within three
years of observation. Using this method, tomographic 21-cm surveys could thus
probe ten orders of magnitude below current CMB constraints on primordial
magnetic fields, and provide exquisite sensitivity to large-scale magnetic
fields in situ at high redshift.
