You can still gather Wood even with the fire out it's just slower. That's the way out of the loop: gather Wood with fire out, then use it to light the fire again (Search for Kindling first if you need it, then Light a Fire, then Feed Fire).
Stone searching unlocks after you've fed the fire a couple of times once you've done that you'll see "Search for Stone" appear in the Actions tab. So the sequence is: gather Wood → light fire → feed fire a few times → stone search unlocks → gather Stone → build Fire Circle.
It's a tight early loop but once the Fire Circle is up the fire stays lit long enough that it stops being a constant crisis.
Hope that helps.