That is to say, there seems to be a gap between admitting that all
knowledge is based on experience, or "observation and the
hypothetico-deductive method", and admitting that all knowledge is
uncertain
The answer to that would come from his doctrine of meaning holism, first expounded in the last section of his famous essay "Two Dogmas of Empiricism", Empiricism without the Dogmas.
Meaning holism holds that the distinction between analytic and contingent propositions is a matter of degree. Analytic propositions, including the theorems of logic, are simply propositions that are recalcitrant to the test of further experience, but are in principle revisable. Contingent propositions, of which there are many gradations, are closer to the tribunal of experience.
Quine uses the analogy of a "web of belief" to illustrate this view, in which beliefs hold together with some measure of coherence. Beliefs closer to the center are more dependent on other beliefs, whereas beliefs closer to the boundary of experience are more dependent on experiential/empirical input. To give an example: If I believe that there are three trees in my backyard, that statement is more easily revisable from experience than my other belief that matter consists of fields of force. The former statement contains terms that get their meaning more from perceptual input, whereas the latter statement contains terms that are lodged in complex theoretical schemes.
That is to say, both statements get their meanings from both experience and other terms (intesionality), but one is by gradation more easily revisable than the latter because it's meaning is less theoretically dependent than the latter. Both are, in principle, revisable but to revise the first we need to adjust very few other beliefs, while to revise the second we'd have to adjust many other beliefs that hold theoretically together.
Logic, in this picture, is more or less a formalization of broad-scale invariances that are also indirectly dependent on experience/empirical input. That is, everything hinges on the cleavage of the web of belief to the perceptual boundary, but the deeper in the web beliefs are lodged, the harder to revise they are, because they depend on chains of beliefs and interdependent conceptual schemas.
You may find this characterization of logic unsatisfactory. If so, tell me why and I can try to explain how Quine would answer to the best of my ability and to the extent of my knowledge of Quine.
I hope this somewhat answers your question!