Neutrino interactions with protons and neutrons probe their deep structure and may reveal new physics. The higher the neutrino energy, the sharper the probe. So far, the neutrino-nucleon (nu N) cross section is known across neutrino energies from a few hundred MeV to a few PeV. Soon, ultra-high-energy (UHE) cosmic neutrinos, with energies above 100 PeV, could take us farther. So far, they have evaded discovery, but upcoming UHE neutrino telescopes endeavor to find them. We present the first detailed measurement forecasts of the UHE nu N cross section, geared to IceCube-Gen2, one of the leading detectors under planning. We use state-of-the-art ingredients in every stage of our forecasts: in the UHE neutrino flux predictions, the neutrino propagation inside Earth, the emission of neutrino-induced radio signals in the detector, their propagation and detection, and the treatment of backgrounds. After 10 years, if at least a few tens of UHE neutrino-induced events are detected, IceCube-Gen2 could measure the nu N cross section at center-of-mass energies of root s approximate to 10-100 TeV for the first time, with a precision comparable to that of its theory prediction.