This is a difficult conceptually. I agree. We currently have no evidence that suggests our 4-dimensional universe is embedded in some higher dimensional space.
For a sphere embedded in a 3-dimensional space, you can elect to use intrinsic or extrinsic geometry. Both will give you the same measurements.
But in our universe, there is not higher-dimensional embedding space we can refer to. So we are stuck with intrinsic geometry. How I think about it is this: there is really no reason that it must be true that, for example, a triangle has interior angles summing to $180^o$ or that the dot product of basis vectors is zero. Any of these geometric elements that are postulates in Euclidean geometry aren't inherent truths about the Universe. They're just what we see in our everyday experience. That is, they're in a sense empirically discovered.
So how do you discover intrinsic geometry empirically? You measure angles, you measure dot products and you see what the values are. If those values are what you'd get with flat space, you're in a flat space. If they're what you'd get in curved space, well, you're in a curved space. You can consider this the definition of a curved space. You don't have to envision space bending into some other space. Just that in our space, we measure dot products of basis vectors to have some non-zero value.
In response to your edit:
Specifically and by definition what it means for a space to be intrinsically curved --- like all these answers say --- is that when you take geometric measurements they don't come out the way Euclidean geometry predicts.
We call it "curvature" because it works exactly like curvature. Angles and distances measured are exactly what they would be if the space was curved. We don't assume an embedding space because we don't need to to get the right answers. So why add something to the theory that cannot be observed?
Intrinsic and extrinsic curvature are connected in that they both make the same predictions. Just how you do the math is a bit different. If you don't exist in the embedding space, then you can't use the tools of extrinsic curvature to take measurements. You have no choice but to measure things intrinsically.
Unless you can observe the embedding space, then no, you cannot deduce that you exist embedded in a higher space. That's an assumption that cannot be tested.