Is there some theory which predicts that the speed of light in vacuum is constant for all observers? Relativity theory takes this result for granted because it's one of its assumptions. Is there some theory which starts with some even more basic assumptions and then predicts that the speed of light is constant for all observers?
 A: Well, in some sense, yes. Maxwell's electrodynamic theory is this theory. It follows from Maxwell's equations as a mathematical fact that $c=\sqrt{\dfrac{1}{\mu_0\epsilon_0}}$. Thus, one can say that Maxwell's theory predicts that in whichever frame Maxwell's equations are true, the speed of light in the vacuum has to be $\sqrt{\dfrac{1}{\mu_0\epsilon_0}}$. Now, it is an empirical fact that Maxwell's equations are valid in all inertial frames. Thus, in a way, Maxwell's theory predicts that light's speed should be the same in all inertial frames. 
Edit
Inspired by the answer of Ringo Hendrix, I would like to add this view at answering the OP's question: 
Remember that in Special Relativity, there are two postulates: 


*

*Principle of Relativity: Laws of Physics are the same in all inertial frames. 

*Invariance of the Speed of Light: Speed of light is equal to $\sqrt{\dfrac{1}{\mu_0\epsilon_0}}$ in vacuum in all the frames of references.
As described in this wonderful paper called "Nothing but Relativity", the author derives the most general transformation relation consistent with the first postulate of special relativity, homogeneity of space and time, and isotropy of space. This transformation reads as follows: 
$x'=\dfrac{x-vt}{\sqrt{1-Kv^2}}$
$t'=\dfrac{t-Kvx}{\sqrt{1-Kv^2}}$
where the standard symbols have their usual meaning and $K$ is an undetermined universal constant. From this framework, it can be easily seen that if Bob is moving at $u$ wrt Alice and Charlie is moving at $v$ with respect to Bob then Charlie will be moving at $\dfrac{u+v}{1+uvK}$ wrt Alice. This means that if $v=\sqrt{\dfrac{1}{K}}$ then and only then Charlie's speed in Alice's frame would also be equal to $v$. This means that there exists a unique invariant speed $\sqrt{\dfrac{1}{K}}$ and we have derived this using only the first postulate. Now what the second postulate does is it determines the value of $K$. Of course, it does so by (essentially) using the theory of Maxwell. 
A: I think, it is brought about by the fact that $c=\frac{1}{\sqrt{\mu\epsilon}}$. So, in a medium, irrespective of your motion relative to the medium, your experimental observation of the value of $\mu$ and $\epsilon$ of the medium doesn't change, hence it preserves the speed of light of the medium.
A: On the Wikipedia page, https://en.m.wikipedia.org/wiki/Derivations_of_the_Lorentz_transformations, under the section "From Group Postulates", one can deduce that there is a constant speed for which time goes to infinity and such. 
In a sense, the speed of light is derived as a constant when deriving Lorentz transformations just from Group theory. It appears as the maximum value of speed before time starts becoming imaginary. Hence, a constant maximum speed is derived: the speed of light in a vacuum.
