This could be years of work to decommission the fuel rods, never mind anything else. Look how long the decommissioning has been going on at UK sites like Dounreay and Sellafield.
I'm not entirely sure that the term decommission is appropriate for fuel rods themselves. Reactors and sites are decommissioned over long periods of time as you point out.
But when it comes to the spent fuel, the approach has generally been to leave them in fuel pools at reactor sites for ages. As pools have become full, some of the older fuel bundles have been moved to dry cask storage, again usually on-site. Since the heat the fuel gives off decreases over time, its possible to move fuel from pools to dry casks in time periods such as 5 years after the fuel was last used. But again in practice its often been done much more slowly than that, and operators have often favoured refitting their spent fuel pools to cram more fuel in. In the case of Fukushima, I expect the common spent fuel pool was built later on in order to deal with the individual reactor pools filling up, but I believe they also have some dry cask storage on-site too.
Some countries, such as the UK and France indulged in a lot of fuel reprocessing instead, but this agenda has obviously hit various snags at times and still leaves plenty of radioactive waste.
Certainly when it ones to decommissioning the reactors at Fukushima and removing the melted fuel from the broken reactors, they have talked about 40 year timescales. But this is considered optimistic by many, due to a large number of complications. Decommissioning a reactor that didn't melt down is tedious, decommissioning one with fuel that has escaped the reactor pressure vessel due to core meltdown is uncharted territory that requires technologies and solutions that are presently unavailable.
There is also a lot of other radioactive material, e.g. debris currently stored in containers, at the Fukushima site. Whether this and the spent fuel ever gets moved elsewhere may depend on whether they ever manage to decommission the reactors and remove the melted fuel. If they fail to do that, perhaps they may as well keep a lot of radioactive shit at the site indefinitely.