> Besides the fact that measurement at that level is actually interaction, how can you prove that both particles were not having the same state from the start?

You can't get the same results that you get with entanglement if there is some kind of internal "agreement" among the particles from the start. I think the clearest example of how that kind of thing cannot reproduce the results that you actually get with entanglement is a thing called the CHSH game.

The CHSH game goes like this.

You have two players, A and B. When the game starts, A and B are sent to separate locations, very far apart (say, a light-day apart), and the two locations will be at rest relative to each other (quantum is confusing enough...let's keep relativity out of this!).

At each of those locations, there is a referee. The referee has a true random number generator, which he uses to generate 1000 random bits, one at a time. After each bit is generated, the referee tells the player the bit, and then the player selects a bit, 0 or 1.

Once the players have picked their bits, they are brought back to the original location, and they are scored. Scoring works thusly:

For i = 1 to 1000, the players get 1 point if and only if the AND of the referees i'th bits == the XOR of the player's i'th bits. In other words, if the player's bits matched, then the players get a point if either or both refs had 0. If the player's bits do not match, they get a point only if both refs had 1.

Before the game starts, the players are allowed to work out a strategy for the game, and they are allowed to bring anything with them that they want.

Without using entanglement, the best strategy for the players is to agree to both pick 0 every time. They will get the point 75% of the time that way.

With entanglement, though, they can do better. They prepare 1000 entangled qubit pairs in the state (|00⟩ + |11⟩)/√2, and they each take one qubit from each pair with them when they are separated. They also agree on a common reference so that when they do measurements on their qubits they can orient their bases in a particular way as described below.

When player A is told the i'th bit, A takes the qubit from the i'th entangled pair, and if the ref's bit was 0 measures this in the {|φ0(0)⟩ , |φ1(0)⟩}, and if the bit was 1, A measures in the {|φ0(π/4)⟩ , |φ1(π/4)⟩} basis. The result of this measurement is the bit the player chooses.

B does similar, except B uses the {|φ0(π/8)⟩ , |φ1(π/8)⟩} if the ref gives a 0, and the {|φ0(−π/8)⟩ , |φ1(−π/8)⟩} for a 1.

Here's a diagram showing the angular relationships between these basis, in degrees:

B1 B0
| |
| 0 | 45
+--------+--------+--------+
-22.5 | 22.5 |
| |
A0 A1

Notice that when either player sees a 0, then no matter what the other player sees, they are measuring their qubits using bases that are 22.5 degrees apart. When both players see 1, then they end up using bases that are 67.5 degrees apart.

The probability of their measurements agreeing is cos^2 of the angle between the bases. This terms out to be 85.4% of the time when either sees a 0 and so they use bases 22.5 degrees apart, and so they get the point 85.4% of the time in that case.

When both see a 1, and they use bases 67.5 degrees apart, the probability of agreeing is 14.6%, but since in the case of both seeing a 1 they want to disagree to get the point, they get the point 85.4% of the time in this case too.

So, overall, using their entangled qubits, they get the point 85.4% of the time, which is much better than the 75% of the time non-quantum approaches give.

If you replace the spooky entanglement with something where the qubits' state was determined at the start, the above does not work. You only win 75% of the time.

Obviously, no one has literally played the CHSH game as described above, but they have done equivalent experiments, and the result is a better score than you could get without the spooky entanglement.