Are randomness and probability really logically dependent notions? Background
Some have lamented that it is difficult to distinguish randomness from probability, but I seem to be having a contrary difficulty: are they even logically dependent notions?
Probability
While introductions to Statistics abound that will take for granted a relationship between probability and the notion of randomness, I am finding this relationship to be more optional as I read into the foundations of probability theory. It seems that probability theory doesn't require a notion of randomness to satisfy the axioms of Measure Theory and Kolmogorov. Some disciplines, such as Ergodic Theory, even compute expectations (which involve probability measures) on purely deterministic systems.
Randomness
Randomness itself doesn't appear to be a precise notion. Most often I see definitions similar to "the property of being unpredictable". One can notice that some systems can be extrinsically random in the sense that there are models that reduce previously-unpredictable phenomena into a pseudorandom process. According to Chaos theory, this can simply be a matter of knowing the governing equations and the relevant initial conditions with enough precision. Perhaps aspects of Quantum Mechanics are instrinsically random, but even that is not a given in my view.
The closest I have found to a formal notion of randomness is information entropy, which itself goes back to being a consequence of probability theory.
All it seems to take is complexity resulting from not knowing the state-transition rules or the state of a system and we seem to get randomness.
Summary
In summary, (1) probability theory doesn't seem to need a notion of randomness and (2) it is not clear whether randomness is anything more than limited predictability when relevant details are missing. At a glance these notions seem inseparable, but after a long gaze they seem to be at-most in a casual relationship.
Question
Who can I read that really cuts into the meat of this problem?
 A: For some reason, this type of question, although common, does not seem to have a lot of answers to be found. So let us try to answer it here.
First of all, to define randomness we need to define a context. That first step may not seem obvious so we belabor that point a bit here. Consider, please, that all information is context dependent, and being as we wish to define something that does not contain a certain type of information, we need to specify a context before we can impose an absence of information.
Consider, for example, that we might wish to consider a quasi-infinite sequence of binary numbers; 1's and 0's. That does several things. First of all, that context, although arguably arbitrary, is also quite restricted in the sense that we only allow 1's and 0's, and disallow all other possible characters.
Having imposed that context, we can proceed to define randomness as the absence of any structure to the sequence of 1's and 0's, so it is actually a very simple definition, and that definition lends itself to testing, in fact, such testing has no bounds.
So then probability, what is that? As the OP stated, randomness and probability are strange bedfellows, but they are not entirely unrelated in the sense that to test a sequence of 1's and 0's for a lack of structure, we would have to introduce a new concept, that of the likelihood of finding structure, and if there is truly is none but we intuit a structure, then we have made a mistake. So what then is probability? One thing that probability is that it relates to an estimate of structure within an information context.
Returning to our problem, one probability that corresponds to a lack of structure is a 50% probability of 1's and 0's, but we need a lot more than that, for example, the sequence $10101010101010101010101010\dots$ has an equal probability of 1's and 0's but it is structured, i.e., ever other number is a 0. So in sum, randomness is a pertinent lack structure within a context, which context, although it may seem to be contradictory for it to be so, can be highly structured.
