Time travel in films is always sort of a leap. However, I've always dug the Back To The Future handling of it - he goes back and does start to erase himself. No convenient gimmicks or outs - he really does mess up the time line for himself as much as possible, by threatening his very existence.
That Time Machine story sounds like an interesting take too.