Three-dimensional topological insulators feature Dirac-like surface states which are topologically protected against the influence of weak quenched disorder. Here we investigate the effect of surface disorder beyond the weak-disorder limit using large-scale numerical simulations. We find two qualitatively distinct regimes: Moderate disorder destroys the Dirac cone and induces diffusive metallic behavior at the surface. Even more remarkably, for strong surface disorder a Dirac cone reappears, as new weakly disordered "surface" states emerge in the sample beneath the disordered surface layer, which can be understood in terms of an interface between a topological and an Anderson insulator. Together, this demonstrates the drastic effect of disorder on topological surface states, which cannot be captured within effective two-dimensional models for the surface states alone.