The first example for this usage (in your first reference) is well known and should be clear: "It never rains but it pours". The other two show that "without its being the case that" isn't actually a good definition. There may not be any single English alternative phrase that really works for all such uses of but, but the somewhat non-idiomatic phrase "other than" should come pretty close in meaning in most cases:
It never rains other than it pours. - I.e., it never rains without it pouring as well.
Her Own Tribesmen Never other than Say Her Age Is 300 Years. - I.e., they never ascribe her an age other than (ascribing her) that of 300 years.
I did read the names that one time, and never other than that one time. - I.e., I never read the names other than that one time.
This sense of but appears obviously related to the one in "nothing but the truth". I think it is obvious how this sense could be derived from the meaning outside, which is given by etymonline.com for earlier cognates. In fact, outside works just as well as other than in the third example above and almost works in the first. [edited after comment]
Maybe it only feels obvious to Germans how outside can evolve into except, since German has a word for except with a very transparent etymology: outside = außen, außerhalb, except = außer. (On the other hand, even in English, without has gone through a similar evolution starting with its original meaning outside that is still somewhat current.)
outside is a simple physical metaphor for without, a non-physical relation. When we are thinking of a certain case or situation, an exception is outside the certain case or situation.