I don't see the problem. Switching to e.g. bio-fuels is a problem now because you're diverting established agricultural output from food crops to bio-fuel, reducing the supply of food in the existing market, and driving up prices. If you're "re-booting" civilization, then you don't have an established market to upset, so there aren't the same issues. It might slow things down a bit to have to generate your fuel in renewable ways, but you'd still get there in the end. Burn wood (and re-plant the trees), make ethanol from grain, maybe make the switch to battery power sooner, with solar/hydro/tidal/geothermal sources of energy.
The first electric cars were made in the 1800's, but they didn't get much of a chance then, because fossil fuel powered cars were there. Without fossil fuels, they would probably have been developed faster and become much more significant. Lighter-than-air aircraft were swept aside by fossil fuel powered airplanes, but without the fossil fuels, that type of craft might have developed and prospered, and the skies might be filled with Zeppelins.
Sure, history would take a very different course, but there are plenty of technological paths for human ingenuity to follow without fossil fuels.