The paradox is basically independent of this issue. Suppose you collapse a star into a black hole and let it evaporate. Hawking's calculation (the source of the information paradox) says that the radiation emitted during evaporation is completely unrelated to the state of the star. Once the black hole has evaporated completely, you're only left with Hawking radiation, which contains no information about the star. Information has been lost, hence the paradox.
(Note that you don't have to wait for the black hole to evaporate completely to get a paradox. There is a contradiction as soon as the black hole has lost half its mass to evaporation).
Edit: To the question of whether a black hole will form in the first place, take a look at this related question (in particular the answer by FrankH). Infalling matter will fade out exponentially fast, so that after a very short time it will be virtually indistinguishable from a black hole with nothing at the surface. This object emits Hawking radiation, whether you call it a black hole or not.
But more to the point of the original question, one way to derive Hawking radiation (though this is not how his original calculation worked) is to consider the frame of reference of an infalling observer. In this frame (I think it's just Kruskal-Szekeres Coordinates), nothing is frozen at the event horizon and you see nothing but vacuum. The vacuum has quantum mechanical fluctuations (often described as virtual particles appearing and annihilating). The strong gravity of the black hole 'stretches' these fluctuations in a way that produces Hawking radiation (often described as pulling apart the virtual particles so that they don't get a chance to annihilate).