> How would you know if those things don't match reality? You can't observe reality independently of these methods (experience, belief, logical conclusion, science, etc.).

We don't do it independently of our experiences. We do it by having new experiences. Our experiences are not truth, they can be inconsistent.

> All premises eventually go back to experiences we can all agree on. Even things as basic as "the world exists", "humans exist", etc. You can't transcend/escape that, even with science.

I think we're in a greement here. The issue is that you said this:

> a (obviously purely hypothetical) person who is 100% perfect at understanding and applying logic could always deduce the truth with perfect accuracy - without testing anything.

That doesn't follow unless you assume that your experiences are always true, and that any logical conclusion drawn from your experience then must be true.