Who thought that the Alexander polynomial was the only knot invariant of its kind? I apologize that this is vague, but I'm trying to understand a little bit of the historical context in which the zoo of quantum invariants emerged.
For some reason, I have in my head the folklore:
The discovery in the 80s by Jones of his new knot polynomial was a shock because people thought that the Alexander polynomial was the only knot invariant of its kind (involving a skein relation, taking values in a polynomial ring, ??).  Before Jones, there were independent discoveries of invariants that each boiled down to the Alexander polynomial, possibly after some normalization.
Is there any truth to this?  Where is this written?
 A: I think that V.F.R. Jones told me that he originally thought that it was a variation of the Alexander polynomial. According to J.H.Conway, Lickorish and Millett were working on their version of HOMFLYPT under Conway's nose at Cambridge and not telling him a thing about it. Another thing that Vaughn mentioned was that in the 1980s not many people were looking directly at the braid group until the discovery of the Jones polynomial. This is more or less true. Ralph Cohen certainly was, but in the context of $\Omega^2 S^3.$ 
Specifically, in low dimensional topology there was, naturally, more focus on Bill Thurston's work and the work of his disciples. 
In relation to your follow-up to Dylan's answer, many people would argue that Witten's formulation of the Jones polynomial is a topological definition. 
It seems that a more reasonable answer is yet to come in the form of identifying where the pieces of Khovanov homology come from.
A: The skein relation approach to knot invariants was not very popular before the Jones polynomial.  The Alexander polynomial was thought of as coming from homology (of the cyclic branched cover); Conway had found the skein relation, but it was not well-known.  Of course once you start investigating skein relations systematically, you rapidly find the Jones, Kauffman, and HOMFLY relations.
Basically, people had been looking for invariants using their standard tools like homology, and had trouble constructing interesting invariants that way.  The idea of just looking for a skein relation was new.  The notion of "polynomial invariants" by itself is too vague to give a place to look.
A: You can find some historical remarks on polynomial invariants in chapter 9 of the book
"Knots and links" by Cromwell, he also gives a lot of references.
A: What makes the Jones polynomial dramatic, I think, is not that it is a polynomial invariant per se, but that it came from an unexpected source where nobody had thought of looking. Indeed, there's still no conceptual mathematical explanation for why we should expect knot invariants to come from such a source.
Jones was working on the Potts model in statistical mechanics (how could this possibly be related to topology?). In this context, it was relevant to study representations of the braid group with n strands Bn into the Temperley-Leib algebra TLn. The miracle now is that the Markov trace of the representation of a braid, suitably normalized, is invariant under Markov moves, and is therefore an invariant of the knot obtained by closing the braid. Why should it be a knot invariant, conceptually? Nobody knows.
What makes it even more amazing is that the Jones polynomial turns out to fit into a family with the Alexander polynomial, which is the archetypical algebraic knot invariant, which heuristically suggests that the Jones polynomial is something important which we should be looking at, and which should probably have a sensible topological interpretation.
The Jones polynomial, I think, is "mathematics we can calculate" as opposed to "mathematics we understand", even now, 25 years after its discovery. Yet it turns out to be tremendously powerful, and to have deep connections with other parts of mathematics.
