Given sufficiently god-like technology, you could run a simulation of the entire world repeatedly, modifying variables until you get a world with a copy of Sagan who fits exactly all the historical information available with him. Something like this is implied to be happening towards the end of Stross's Accelerando, which I highly recommend (there's a free ebook edition).

However, note my use of the term "god-like". Anything capable of doing this is so close to being a god that it makes very little difference from our point of view. There's also the theory that our universe is a simulation run by such an entity - the argument is something like "if it is possible to run a simulation of the universe, it is statistically far more likely that we're in such a simulation." Sort of makes sense, if you have the right mind-set or tilt your head and squint.

Quantum randomness. Hate to break it to you, but not happening.

Is it really random or is it that we don't know how all the rules work?

The prevailing theory is that it is truly random. Check out the Wikipedia entry on theories that aimed to eliminate that randomness, called hidden variable theories: http://en.wikipedia.org/wiki/Hidden_variable_theory

That's the information part. I really don't need his own atoms, just the precise pattern they were arranged on a given moment in time. Unless we can find differences between individual atoms of a given isotope, any atom of the right kind will do. Or, if we want to reconstruct just a digital model, we can forgo the atoms and run the simulation on the state representation.

But, like I said, it's a problem to be solved by our smarter successors, not for us.

You don't need to recreate his brain. Collect all the recordings of his voice and photos of his body. Model his body, particularly his chest, throat, and head, until you can accurately reproduce his voice. Then model his speech pattern based on the recordings of his speech, and all you've got left is to hire a few good writers and scientists to write the script.