In The Big Bang (the concluding episode of the Pandorica arc), the Doctor is erased by the cracks in space-and-time. Yet Amy brings him back by remembering him, which is triggered by River Song dropping off her diary with Rory and then walking past the window. Since the Doctor never existed at that point, what made River Song go to Earth and drop off a blank diary with a random stranger?
Spoilers for S6E7, A Good Man Goes To War:
River, being part-Time Lord, probably is capable of remembering people after they're consumed by the crack. She didn't mention this detail in The Big Bang, as it would reveal too much about herself too soon. After the universe was restarted, she remembered the Doctor, and had her journal/diary although the writing in it had been wiped as it no longer happened. So she left it for Amy as a reminder of the Doctor, just like the ring had previously reminded her of Rory.
Likely the same way that the Doctor was able to hide Amy's memories of him in the wedding expression ("Something old, something new, something borrowed, something blue...") despite the fact that at at the time she starts to remember him, he would never had existed to create or hide those memories in any way.
That is to say, impossibly. Perhaps the Doctor managed to hide memories for her as well, albeit less important ones. All he had to do for River is make her remember to drop off a blue journal; Amy's hidden memories had to bring him directly into existence.
On some core level, considering it was possible for him to be remembered back into existence at all and the fact that the Universe corrected itself after his re-appearance (River's journal filling back up, etc.), it seems likely that he never entirely ceased to exist (the same way Amy had dormant memories of Rory after his "non-existence"). However, it seems the one thing that was not corrected was Rory's memories of being an Auton, as the real Rory was brought back and married Amy (but still remembers those years).