Not sure why folks think that all of the natural resources will be used up. I assume that after the decline of one civilization, there are still trees around to make fire? If it takes a hundred million years for a civilization to rise and fall, then it is probably even possible for coal to be regenerated in some or many areas (it can be formed in tens of millions of years[1]). But much better than finding a coal seam would be finding an ancient landfill. When an archaeologist finds a midden today, the only interesting artifacts are bones and stones. But when an archaeologist 200 million years from now finds a midden, it will have high concentrations of rare earth metals useful for advanced electronics. Surely that is a nice jump-start for any new civilization!
Not only that, but lots of uranium will be mined and concentrated as well (assuming it wasn't detonated or taken off-planet in ships). Uranium and thorium have half lives in the billions of years for some isotopes[2]. And if the civilizations care at all for the future, then they will leave knowledge lying about in a durable form (explored in Niven's Footfall, where knowledge was recorded on metal plates).
The advancement of civilization pretty much depends directly on the amount of useful energy the inhabitants can harness. At prehistoric levels, only human power is meaningful. With agriculture and animal husbandry, draft power from animals becomes available and makes it feasible to farm large tracts of land (rather than just subsistence gardens). With fire and metallurgy, steam power eventually becomes available, first from wood and biomass, and later from coal and fossil fuels. But solar power can also be harnessed by dams, and was long before the Industrial Revolution.
Again, if knowledge is passed down in some form to each new civilization, then converting power to electricity would greatly aid the reboot of the next civilization. That's because electricity is one of the easiest ways to convert power from one form to a more useful form. One electrification has been achieved, even the absence of fossil petroleum is not a major deal-breaker. Gasoline has one of the highest energy densities of any chemical fuel (non-nuclear). But ethanol is decent, and can be manufactured from average biomass. At sufficient technology level, gasoline and kerosene can be manufactured from scratch, via thermal depolymerization (TDP)[3].
Even steel is not a problem, because in thousands of years, most of the steel on earth will rust down to iron oxide. No tectonic activity necessary. But let's say that the previous civilization managed to coat most structural steel with really effective anti-rust coatings. No problem. Just chisel off the coatings and let it rust away! But most likely, no steel will be so thoroughly coated as to resist all weathering effects. Steel at the bottom of a lake or ocean will last longer, but will be harder to get at anyway. Unless a civ goes underwater to escape land, most of the steel will probably be on land.
The Mote in God's Eye series also explores the theme of cyclic civilization (a good read!).
[1] http://www.planete-energies.com/en/medias/close/how-coal-formed-process-spanning-eras
[2] https://en.wikipedia.org/wiki/Isotopes_of_thorium#Thorium-232
[3] https://en.wikipedia.org/wiki/Thermal_depolymerization