(Sorry for replying so late, I hope you'll still see this.)
Well, the situation of entanglement is not really* different from the following one:
Imagine you have two pairs of socks, a red pair and a blue pair. Now, certainly you only wear a red (blue) sock on your left foot iff you wear one of the same color on your right foot, right?
So, consider the measurement of your left sock's color by pulling up the leg of your pants and looking at your sock. If it is red, you can be 100% sure you will measure your right sock to be "red" as well, and, similarly, if it is blue you will measure blue on the right, too. Now, in order to explain this phenomenon, do you need faster-than-light travel of your left sock's color to your right sock at any point? No. The results of the color measurements on both sides are just correlated with each other because both subsystems (both socks) were prepared that way earlier.
* Granted, the issue of entanglement is actually slightly more complicated since a sock being either red or blue is not quite the same as the sock being in a superposition of both colors, i.e. being red and blue at the same time. But this difference just boils down to the fact that, in (the Copenhagen interpretation of) quantum mechanics there are measurements whose outcome is non-deterministic and superpositions just encode this very fact (together with complementary observables that allow us to distinguish between pure eigenstates and superpositions in the first place. Without complementary variables we would never see a difference between the two.) So, for instance, in entanglement experiments one often prepares two particles in a superposition of eigenstates of the spin-z operator and then proceeds to measure the particles' spin with respect to another axis. It turns out that the results of both measurements will be random but correlated. Will you able to explain the results using the sock analogy? No, because the socks are entirely classical, in particular deterministic, and there are no complementary variables such as spin x and spin z (e.g. the color of the socks has nothing to do with it being made from cotton or wool and both properties are defined independently). Will you now need non-locality, though? Still no, you just needed to add non-determinism in the form of complementary variables to your theory.
So, put differently, if your theory of quantum mechanics is non-deterministic, then it can very well be local. Only if it is deterministic, it must be non-local (see, for instance, Bohmian mechanics). So, while you could have both, indeterminism and non-locality, at the same time, you certainly don't need both and, in fact, in the standard (Copenhagen) interpretation of quantum mechanics we don't have both. I think the missunderstanding that the Copenhagen interpretation is both non-deterministic and non-local originates from the idea that we imagine the wave function to collapse upon measurement and this collapse to propagate faster-than-light from one entangled particle to the other. But the collapse of the wave function is not just not compatible with special relativity but it is also not compatible with the unitary time evolution of quantum mechanics, so we should consider it merely a tool for us instead of something that is actually happening. What matters at the end of the day are expectation values of measurements and for that you don't need the collapse of the wave function or non-locality at any point.