It isn't difficult to get this loop started "for the first time". All it takes is for the Enterprise, with Data aboard, to visit Devidia II for whatever reason.
Once there, the heroes are sure to pick up the mysterious timewaves, will investigate, and will travel to the past. And once there, they will run into events that sever Data's head "for the first time" and thus ensure that the ship will go to Devidia II on the next loop.
Now, how unlikely an event is a visit to Devidia II? We know the E-D goes places, and might well end up on that one eventually, even if at the time of the eventual loop the location is not on their schedule yet (or they would have mentioned it). And it doesn't much matter when she goes there, because the aliens will supposedly keep on sucking life out of the San Francisco of Mark Twain for a long, long time. The ship could "originally" have visited the planet in 2382 or 2364 (all it requires is for the ship to be intact and for Data to be aboard, and many realities will cater for those, skipping events like ST:Generations or Data's gruesome death in the hands of Pakleds in 2366 or whatever), and the events of the loop would then cause things to settle down to 2368 instead.
That is, whatever happens in the past creates a timeline where the cavern is excavated in 2368 - regardless of what happened in the future. Now how unlikely is that? If you don't want to believe in the events of the 19th century dictating the archaeological or construction minutiae half a thousand years later, you can say that the date of the excavation actually wobbles a little. Again all it takes is for the excavation to happen within Data's career aboard the Enterprise.
Now, the interesting question is whether the loop now is eternal, that is, whether Data's head will always be found and necessarily be sent back to the past to be found again. It all happened once or twice, but did it happen a zillion times, and will it happen again?
Timo Saloniemi