Probably about 5-10 years minimum
Fallout would not be a major long-term problem, the timescale on which radiation due to fallout would present a serious danger would be less than 5 years. See this article which says:
Radioactive material which takes longer than 24 hours to return to earth is called delayed or global fallout. Some of the delayed fallout remains in the troposphere (see Figure 1) for days, weeks or months. This tropospheric fallout usually returns to earth within ten or 15 deg of latitude of the original explosion, mostly by being incorporated in raindrops as they are formed. The clouds of nuclear explosions larger than about one megatonne penetrate partially or wholly into the stratosphere, and deposit fission products there, which become stratospheric fallout. Since the stratosphere has no rain formation and is less turbulent than the troposphere, radioactive particles in the stratosphere can take months or years to return to earth. During this time the particles can move to any part of the globe.
By the time stratospheric fallout reaches the earth, its radioactivity is greatly reduced. For example, after one year, the time typically required for any sizable amount of fission products to move from the northern to the southern stratosphere, the rate of decay will be less than a hundred thousandth of what it was one hour after the blast. It is for this reason that stratospheric fallout does not have the potential to cause widespread and immediate sickness or death.
According to recent climate modeling, the big problems which could delay a return in your scenario would be:
Nuclear winter due to smoke particles remaining in the upper atmosphere for years, which would cool and darken the world enough to make growing crops difficult for several years after
Destruction of a lot of the ozone in the ozone layer, which would greatly increase the amount of dangerous ultraviolet radiation from the Sun that reached the surface, harmful to both people and crops.
Nuclear winter
Climate scientist Alan Robuck has done a lot of research on the effects of nuclear war, and has posted a large number of links to papers and articles on the subject on this page. He also has a good review article from 2010 online here. One point he notes on p. 420 of that article is that the nuclear winter effects would be exacerbated by the fact that cities and industrial facilities would likely be targeted, as opposed to the more uniform spread you seem to suggest in your question (which would make less sense politically and would have less damaging effects). If these areas are targeted it should produce an especially large amount of soot and smoke:
Megacities have developed in India and Pakistan and other developing countries, providing tremendous amounts of fuel for potential fires. Following the flash of light comes the blast wave (like thunder following lightning) which will break apart many structures and blow out the flames, but crumpled structures burn more easily and fires would be reignited by burning embers and elec- trical sparks. Imagine how easily a house would burn with open gas lines or a filling station with gas pumps knocked over. In fact, there are many flammable sources of fuel for fires in cities, including buildings and their contents, trees, and even asphalt. Modern materials, such as plastics, not only burn with a sooty smoke, but also produce high levels of toxic chemicals. ... The climatic effects of the use of nuclear weapons depend on the amount of smoke they would generate, and this depends on the targets. Nuclear targeting plans call for not only cities to be targeted, but also industrial facilities such as oil refineries and wells. Forests around military targets would also provide fuel. All these targets together would produce clouds of black sooty smoke, which rise into the atmosphere.
Most of the modeling has investigated the effects of smaller-scale nuclear conflicts, like a nuclear war between India and Pakistan, but we can at least use the results of these studies as a sort of lower bound on what would happen in your scenario. And at least one recent study has modeled a global nuclear war with the full arsenal, the 2007 paper "Nuclear winter revisited with a modern climate model and current nuclear arsenals: still catastrophic consequences". This study used a preexisting global circulation model, Model E from the NASA Goddard Institute for Space Studies, which is mainly used for climate issues unrelated to nuclear winter, like modeling global warming along with past climate change. The authors of the paper note on p. 3 that "This climate model has been tested extensively in global warming experiments [Hansen et al., 2005; Schmidt et al., 2006] and to examine the effects of volcanic eruptions on climate. The climate model (with a mixed-layer ocean) does an excellent job of modeling the climatic response to the 1783 Laki [Oman et al., 2006b] and the 1912 Katmai [Oman et al., 2005] volcanic eruptions."
The paper estimates that about 150 teragrams of smoke would be released in a full nuclear conflict. As discussed on p. 6, the effects on global temperature would be dramatic for several years after, and even after 10 years they'd be comparable to temperatures in the last ice age (though of course there were warmer areas where farming would have been possible back then):
A global average surface cooling of –7 °C to –8 °C persists for years, and after a decade the cooling is still –4 °C (Fig. 2). Considering that the global average cooling at the depth of the last ice age 18,000 yr ago was about –5 °C, this would be a climate change unprecedented in speed and amplitude in the history of the human race. The temperature changes are largest over land … Cooling of more than –20 °C occurs over large areas of North America and of more than –30 °C over much of Eurasia, including all agricultural regions.
The 2010 article had a graph of the temperature change observed in the model from the above 2007 paper, given a nuclear war in 2006, with the full-scale war releasing 150 Tg of smoke shown in brown:
Robuck also notes in the article that even in the case of a much more limited nuclear exchange which only put 5 Tg of smoke into the atmosphere, after 10 years the global temperature would still be 0.5 °C cooler than before, which is a bigger deal than it might sound:
even after 10 years the temperature would still be 0.5 °C colder than normal. These numbers might not seem like much, but even during the Little Ice Age, global temperatures were only about 0.5 °C below normal. Every once in a while large volcanic eruptions produce temporary cooling for a year or two. The largest of the past 500 years, the 1815 Tambora eruption in Indonesia, produced global cooling of about 0.5 °C for a year. Year 1816 became known as the ‘Year Without a Summer’ or ‘18 hundred and froze to death’. There were crop-killing frosts every month of the summer in New England. The price of grain skyrocketed, the price of livestock plummeted as farmers sold the animals they could not feed, and a mass migration westward from the US East Coast across the Appalachians to the Midwest began. In Europe, widespread famines occurred ... A nuclear war could trigger declines in yield nearly everywhere at once, with strong impacts on the global agricultural trading system.
As for the question of farming after a global nuclear war, he says on p. 423:
Not only would it be virtually impossible to grow food for 4–5 years after a 150-Mt nuclear holocaust, but it would also be impossible to obtain food from other countries.
And on that page and the next he discusses some of the reasons farming would become so difficult in the aftermath:
There are many ways that agriculture is vulnerable to nuclear winter. The cold and the dark alone are sufficient to kill many crops. Superimposed on the average cooling would be large variations. During the summer of 1816 in New England, there were killing frosts in each summer month.30 Only 1 day with the temperatures below freezing is enough to kill rice crops. Colder temperatures mean shorter growing seasons, and also slower maturation of crops; the combination results in much lower yields. Most of the grains that are grown in midlatitudes, such as corn, are actually of tropical origin, and will only grow in summer-like conditions. For example, a study done in Canada shows that with summer temperatures only 3 °C below normal, spring wheat production would halt.8 Insufficient precipitation would also make agriculture difficult.
Finally, p. 5 shows a large drop in global precipitation, down to about 45% of its current value in years 2-4 for the 150 Tg case (the black line with open circles in the top graph):
Ozone layer
Unfortunately the 2007 paper which models global nuclear war didn't model ozone loss, and just noted other studies had found "global ozone loss is likely". I couldn't find any recent papers modeling the effects of a global nuclear war on ozone, but this paper from 2008 deals with a more limited nuclear exchange that puts 5 Tg of smoke into the upper atmosphere, with these results:
We calculate large losses in total (column) ozone that persist for years after the soot input. The global mean ozone column remains depleted by 20–25% for 5 years after the injection (Fig. 1). Catalytic destruction during the transport of air poleward compounds ozone loss at high latitudes. Throughout the first 5 years, total ozone depletions are 25–45% at midlatitudes and 50–70% at northern high latitudes.
In the discussion section they talk about biological consequences:
Conclusive evidence shows that increased UV-B radiation damages aquatic ecosystems, including amphibians, shrimp, fish, and phytoplankton (13). The effects of sunlight on the biota are quantified as a product of the sun's spectrum at the Earth's surface and the action spectra for biologically damaging processes, such as erythema, carcinogenesis, and photoinhibition. An analysis of biological sensitivity to UV spectral changes concluded that a 40% ozone column depletion at 45°N – as computed here – would increase DNA damage (believed related to carcinogenesis) by 213%, and plant damage (e.g., photoinhibition) by 132% relative to normal conditions (14). The smallest ozone column losses are predicted to occur in the tropics, where self-healing limits depletion to ≈10% during the first 3–4 years. Although we found no studies of biological impacts of ozone loss in the tropics, the midlatitude analysis concludes that a 10% column loss would increase DNA damage by ≈28% (12, 14). Ozone losses at midlatitudes point to DNA effects in the range of 150% for five years or more. The biological implications should be further investigated.
Similarly, this paper from 2014 also models a limited exchange adding 5 Tg of smoke to the air. As summarized in the paper's abstract:
Our calculations show that global ozone losses of 20%–50% over populated areas, levels unprecedented in human history, would accompany the coldest average surface temperatures in the last 1000 years. We calculate summer enhancements in UV indices of 30% – 80% over midlatitudes, sug- gesting widespread damage to human health, agriculture, and terrestrial and aquatic ecosystems. Killing frosts would reduce growing seasons by 10 – 40 days per year for 5 years. Surface temperatures would be reduced for more than 25 years due to thermal inertia and albedo effects in the ocean and expanded sea ice. The combined cooling and enhanced UV would put significant pressures on global food supplies and could trigger a global nuclear famine.
More details on the ozone loss on p. 168:
As in Mills et al. [2008], we calculate massive ozone loss as a consequence of these extreme stratospheric temperatures (Figure 8). Consistent with that work, we calculate a global average column ozone loss of 20%–25% persisting from the second through the fifth year after the nuclear war, and recovering to 8% column loss at the end of 10 years. Throughout the first 5 years, column ozone is reduced by 30%–40% at midlatitudes and by 50%–60% at northern high latitudes.
Pages 172-174 discuss the effects of increased ultraviolet radiation from ozone loss on plants and animals:
Pierazzo et al. [2010] reviewed literature considering the effects of large and prolonged increases in UV-B radiation, similar to those we calculate, on living organisms, including agriculture and marine ecosystems. General effects on terrestrial plants have been found to include reduced height, shoot mass, and foliage area [Caldwell et al., 2007]. Walbot [1999] found the DNA damage to maize crops from 33% ozone depletion to accumulate proportionally to exposure time, being passed to successive generations, and destabilizing genetic lines. Research indicates that UV-B exposure may alter the susceptibility of plants to attack by insects, alter nutrient cycling in soils (including nitrogen fixation by cyanobacteria), and shift competitive balances among species [Caldwell et al., 1998; Solheim et al., 2002; Mpoloka, 2008].
The ozone depletion we calculate could also damage aquatic ecosystems, which supply more than 30% of the animal protein consumed by humans. Häder et al. [1995] estimate that 16% ozone depletion could reduce phytoplankton, the basis of the marine food chain, by 5%, resulting in a loss of 7 million tons of fish harvest per year. They also report that elevated UV levels damage the early developmental stages of fish, shrimp, crab, amphibians, and other animals. The combined effects of elevated UV levels alone on terrestrial agriculture and marine ecosystems could put significant pressures on global food security.
The ozone loss would persist for a decade at the same time that growing seasons would be reduced by killing frosts, and regional precipitation patterns would shift. The combination of years of killing frosts, reductions in needed precipitation, and prolonged enhancement of UV radiation, in addition to impacts on fisheries because of temperature and salinity changes, could exert significant pressures on food sup- plies across many regions of the globe. As the January to May 2008 global rice crisis demonstrated, even relatively small food price pressures can be amplified by political reactions, such as the fearful restrictions on food exports implemented by India and Vietnam, followed by Egypt, Pakistan, and Brazil, which pro- duced severe shortages in the Philippines, Africa, and Latin America [Slayton, 2009]. It is conceivable that the global pressures on food supplies from a regional nuclear conflict could, directly or via ensuing panic, significantly degrade global food security or even produce a global nuclear famine.
And remember, both the studies above deal with the 5 Tg of smoke scenario, a full-scale nuclear war was predicted to put about 30 times that much smoke into the upper atmosphere, presumably having a significantly larger effect on the ozone layer.
