There is another option I have never seen used in fiction: understand what the time machine is really doing with respect to conservation of matter. The reason that time travel paradoxes arise is that we focus on macroscale elements, like a person (who may not be conserved), instead of microscale elements, like atoms (which definitely will be conserved by Conservation of Matter laws).
Let's consider a single atom going back into time first.
At 3pm, there's a single atom, Alpha, happily bouncing around.
At 9pm, John sends Alpha back to 3pm.
Now there are two Alphas bouncing around. Let's call them Alpha+0 and Alpha+6 since the second one is subjectively 6 hours older.
Six hours later, the time is 9pm again.
If Alpha+6 didn't change history, then John sends Alpha+0 into the past -- no paradox, no complication. After 9pm, Alpha+6 is now the only instance of Alpha in the world.
But perhaps Alpha+6 did change history and John isn't around any more to run his experiment. Now what happens? In my idea, Alpha+0 STILL GOES INTO THE PAST. Alpha+0 might not be at the machine, and John might not be around, but Alpha+0 still exists somewhere in the world. In my idea, once John has created a wormhole-like connection from the present to the past, that connection exists, regardless of how the past changes. The wormhole endpoint is moved around such that at 9pm, it is always in the location of Alpha+0 and so Alpha+0 always goes to the past, even if Alpha+0 is part of some other molecule in the new timeline.
Let's say Alpha+0 was an oxygen atom. In the original time, it was a free oxygen, not part of any molecule. In the new time, because of Alpha+6 interference, Alpha+0 gets bonded with two hydrogen to become water. Doesn't matter. At 9pm, that wormhole opens up and swallows the oxygen, cutting the two hydrogen loose.
Now, let's consider sending a person back.
At 3pm, John and Mary have tea. John convinces Mary to be the first time traveler. Mary drinks her tea and agrees. She comes to the lab. At 9pm, John sends Mary back to 3pm.
There are now two Marys in the world... Mary+0 and Mary+6.
If Mary+6 wanders off somewhere and doesn't interfere with her own timeline, then eventually it is 9pm again, and John sends Mary+0 into the past, leaving Mary+6 as the only Mary in the world once again. Great!
BUT... what happens if Mary+6 does interfere with her own past? Mary+6 goes to that tea -- before they drink their tea -- and tells Mary+0 that John is not to be trusted. Mary+0 runs away, and she's so sick to her stomach from fear that she vomits on the sidewalk. She drinks some water to clear the taste. John has to find a new candidate. What happens then?
Well, at 9pm, the atoms that make up Mary+0 all fall into wormholes and travel back to 3pm. Not just those atoms. But also the atoms of the tea that Mary+0 would have drunk. And the atoms of the vomit that were originally in her. But NOT the water that she drunk in the changed time. All the atoms go back in time and arrive at the same point that they were sent originally -- which means they arrive configured like Mary+6, with all the memories of Mary+6.
No matter how much Mary+6 changes the past, the atoms that make up her will always travel back in time and arrive arranged as Mary+6.
There's no change she can make that will alter that fact. We get caught on paradoxes because MARY isn't conserved -- she can be disrupted from one timeline to the next. But we can get out of the paradoxes because THE ATOMS THAT MAKE UP MARY are conserved. The only way those atoms don't exist in the alternate timeline is if they somehow undergo fusion or fission. It is trivial to add to our time travel physics the rule, "Any atom entangled with a time-travel wormhole has enough energy to maintain its coherence... you can heat or pressure it as much as you want, but it won't undergo fusion or fission while it has a date with destiny."
Important: This conservation of atoms concept means that even if time is changed to prevent the time machine itself from being constructed, the time travel will still occur. All the machine does is open the wormholes. Once they're open, they stay open.
It also means that if the time traveler changes history enough, his/her atoms could be a part of important things in the new present, things that will suddenly have holes in them for no apparent reason when those atoms are pulled into the past. There's a lot of story potential there.
If you use this idea in a story, I really want to read it. I've tried to make it work but never quite got it working right. :-)