I hate to answer questions like this because they're very complex ideas that are often attempts at explaining in simpler ways to laymen and the "How/why" questions can be long and not always easy to understand. See this related question with some very nice long and complex answers.
If the mass was swallowed by the blackholes then every single particle
should be inside the event horizon as they brought towards the black
hole at very high velocity and it's becoming difficult to imagine that
some particles were left at the horizon itself
Particles don't have to be retained at the event horizon for information to be retained just outside. This gets tricky, but an image of the particle, not the particle itself is retained. While it's an imperfect analogy, dropping a stone in water creates ripples, which spread out and shrink over time. By carefully analyzing those ripples, you can determine the mass and size of the stone and when it was thrown in.
How is it possible for information to exist at the event horizon?
Information doesn't exist "at" the event horizon. Nothing can exist at the event horizon in a practical sense, stuff passes through the event horizon, but from the perspective of a person some distance away, they see the object falling into the black hole take forever to get there (in reality the visibility red-shifts beyond recognition very quickly), but if you could see it with some kind of super-long-wave imaging device, and a supercomputer to put the information together, you could in theory see everything that ever fell into the black hole by carefully observing the light that escapes from it.
So, nothing is actually encoded on the event horizon (the video got that point wrong). It's all images that take a very long time to reach the viewer from just outside the event horizon due to extreme time dilation.
How exactly can Hawking's Radiation carry the information?
The precise words in the video are
"If information is stored on the surface of a black hole, hawking
radiation has a chance of learning about the information encoded there
and carrying it away"
So, you're asking a question about an "if" and a "chance of", very far from a certainty. I'm not educated enough in the various theories to say how hawking radiation might pick up information from the black hole's formation and history. My limited understanding is that it can't. That Hawking radiation is "new" information so to speak, not carried off bits of old information, but that offends information theory . . . which is a problem for quantum theorists. Please don't take my word for any of this stuff.
Professor Matt Strassler writes a series of articles that try to explain modern physics to people like me and his stuff gets a top review from me. His article on this subject is probably worth a look and he touches on some of the "We don't knows" in better detail. I remember watching one of professor Susskind's lecture on holograms, black holes and information theory on youtube and enjoyed that as well (there's more than one, easily googled, so I won't link).