The measurement of high-energy neutrino-matter interactions furthers our knowledge of nucleon structure and allows us to test proposals beyond the Standard Model: the higher the energy, the more piercing the probe. Ultra-high-energy (UHE) cosmic neutrinos, with EeV-scale energies (1 EeV = 1018 eV), offer the ultimate high-energy probes of neutrino physics. For fifty years, they have evaded detection. Fortunately, upcoming neutrino telescopes have a real chance of discovering them. We perform the first detailed study of the UHE neutrino-nucleon cross-section measurement capabilities, geared to IceCube-Gen2, the planned upgrade of the IceCube neutrino telescope. The sensitivity to the cross section stems from the effect of in-Earth attenuation on the UHE neutrino flux. We work with several models of the UHE ν flux proposed in the literature. In this way, we span the parameter space from pessimistic to optimistic scenarios. To relax the model dependence of our analysis we measure both the cross-section and the flux normalization. Hence, the spectral shape of the ν flux is the only assumed information. Further, we study the dependence of the results on the detector characteristics. This includes the exposure time, angular resolution, radio antenna type. We find that, for the highest flux models, the UHE neutrino-nucleon cross section will be measured to within the theory uncertainty in the cross-section prediction.