The method of forcing certainly fits here. Before, set theorists expected that independent results would be obtained by building non-standard, ill-founded models, and model theoretic methods would be key to achieve this. Cohen's method begins with a transitive model and builds another transitive one, and the construction is very different from all the techniques being tried before.
This was completely unexpected. Of course, in hindsight, we see that there are similar approaches in recursion theory and elsewhere happening before or at the same time.
But it was the fact that nobody could imagine you would be able to obtain transitive models that mostly had us stuck.