Rule #1: The Doctor lies.
Most of the time, when the Doctor says, "I can't...", he's eventually shown to really mean, "I really, really, really shouldn't, but if I really had to, or really wanted to, I could."
The most clear example of this is the 1964 story, The Aztecs. The Doctor spends most of that story adamant that time cannot be changed. This notion is quietly dropped as too limiting for the writers, with the in-universe result that the Doctor is basically caught by we the audience in a lie which he's never directly called on by his companions. Since then, he never makes this claim; indeed, he's more likely to admonish the opposite when confronted by a companion saying something like, "But the world didn't end in 1980!" (Sarah Jane Smith, Pyramid of Mars).
(Of course, keep in mind that, in the days the Classic Series was being made, television was seen as an ephemeral medium. The BBC rarely reran anything, there was no home video, and no notion there ever would be. Hence, continuity was really just not seriously considered!)
Similarly, we see in "The Waters of Mars" that even supposedly "fixed points" can be changed. It just doesn't necessarily turn out very well when they are.
And finally, there are three canonical occasions in the Classic Series in which the Doctor not only crossed his own time stream but actually shook hands with himself, aptly named The Three Doctors (1973), The Five Doctors (1983) and The Two Doctors (1985); and one semi-canonical occasion so far in the Modern Series, the short "Time Crash".
Lastly, there's some reason to infer that River Song's tangled timeline is, in fact, laden with paradoxes (thus not really giving the lie to the Doctor's statements).
