Without getting into the mess of trying to define exactly what a random sequence of bits is, a mathematical proof of their existence would have to be either constructive or non-constructive. If it were constructive it would give a computational algorithm to produce a random sequence; by any definition it would be predictable and hence not random. If the proof were non-constructive it would be essentially useless. Take the set of all infinite sequences of 0's and 1's; it is uncountable. The set of all computational algorithms is countable. Therefore there are an uncountable number of infinite sequences of bits which cannot be produced by any computational algorithm i.e. they are random. So in the world of mathematics, random sequences exist but we are incapable of displaying them --- useless.
The crux of your argument is whether it is possible to encapsulate the objective nature and evolution of the universe in a set of mathematical formulae or, if physics uses mathematics can only describe our interactions with the universe with various models. While the belief in ultimate mathematical laws of nature is widespread it is not universal:
"Law without law" James Archibald Wheeler in "Quantum Theory and Measurement" ed J. A. Wheeler & W. H. Zurek 1983 also available online: http://what-buddha-said.net/library/...ithout_law.pdf
"Are there dynamical laws?" by J. Anandan, Found.Phys. 29 (1999) 1647-1672 also available online at Arxiv:quant-ph/9808045v4.
Interesting. I am not sure if this was your point, but since there are uncountable random sequences which cannot be described by math, then you could have a universe in which the quantum events are dictated by a finite or infinite string of random numbers.
And then if you assume Max Tegmark's view that the universe is a mathematical object, and all mathematical objects exist, then that would mean that if there was one universe which had events dictated by random strings of numbers, then there would be infinite universes like that, each with a different random string of digits dictating events in that universe, and so these events would seem genuinely random to observers inside the universe, no matter how much data they collected, because there is no algorithm dictating the events, they are dictated by the random string of digits.
However, this would not be indeterministic, because the whole future of the universe would be spelled out in the string of random digits.
Edit: I saw your link to the article titled "Law without Law". Logically, you can't have something and not have it. This is an example of what I mean by logically impossible. Basic logic says that A and ~A cannot both be true, yet this is the type of thinking that I believe is required for true indeterminism. i.e. true indeterminism is logically impossible, which is why there is so much confusion about quantum mechanics, because the fundamental idea (that the quantum events are truly random) goes against basic logic. Despite their fundamental assumptions being wrong, their math (the Schroedinger wave function) was correct, and was experimentally verified, so people began to believe their fundamental assumption too.
So this is why you had people like Feynman talking about how no one understands quantum mechanics, because the idea that events can be truly random is impossible.
But, if you look at it from the Everett Many Worlds approach (which I admit I don't understand very well, but I know the overview and the implications of it) then these logical impossibilities that seemed to be real, suddenly disappear.
So what I am saying is that, the universe MUST obey logic. The early quantum mechanics pioneers confused themselves by taking the assumption that it is possible for events to be truly random, which I believe fundamentally violates logic. People should have figured this out sooner, they should have realized right away that if something does not obey the rules of logic, it must be wrong, but the excellent predictions of the Schroedinger wave equation, and the lack of a good alternative interpretation, made people believe it.