> The black hole information paradox implies that there is no way for information to escape the black holeNot quite. When Hawking radiation is included, it becomes possible in principle for information to escape the hole. That's not the main issue.
The main issue is that any information carried by an object that falls into the hole and hits the singularity inside the black hole gets destroyed. So either that information is lost, which violates QM unitarity, or the information has to get copied into the Hawking radiation that gets emitted, which violates the QM no cloning theorem.
> One suggestion have been that the information actually never enters the black hole in the first place, it's just spread out over the surface of the event horizon.
This doesn't really help, because the information can't just stop at the horizon; if an object falls in, it carries its information with it. So "spread out over the surface of the event horizon" really has to mean the information gets copied there, which, as above, violates the QM no cloning theorem. Some physicists, such as Susskind, claim that this actually isn't an issue because no single observer will ever observe both copies of the information, but this argument strikes me as contrived (and I don't think it's been proven that it must be the case).
Two possible resolutions that seem to me to at least avoid the problems I stated above are:
(1) Quantum gravity effects change the singularity inside the black hole to something else: one commonly suggested possibility is that a "baby universe" is born there, and that baby universe carries the information that fell into the hole. In other words, the information stays inside the hole and doesn't come out in the Hawking radiation, but it doesn't get destroyed either.
(2) Quantum gravity effects prevent a true event horizon and a true black hole from ever forming in the first place. That means there is never any singularity or any place where information ever gets destroyed; quantum gravity effects end up converting all of the objects that fell into the "hole" (which is now not a true black hole, but will still look like one to us on the outside, at least for a very long time) into the Hawking radiation that the hole emits as it evaporates. So no information ever gets destroyed and no information ever gets cloned.