Aren't the oldest fossils we know of assumed to be something like 500 million years old?

Or you could try leaving particular "signatures" of radioactive elements. Not ones with a short half-life, obviously, but xenon-124 lasts pretty long, tellurium-128 will survive anything except the heat death of the universe, and there's a few others like that.

Sure, how many >300 million year old fossils have we found related to how many animals lived at that time, over that span of time? The problem is many methods might work -- literally you accidentally falling on a trip to Florida might work -- but the probability can be very low.