Can't quantum teleportation be superluminal some percentage of times?

This is really a subtle point. You are right that in 25% of the cases, Bob will randomly chose the "correct" measurement basis and thus get the correct value.

However, there is no way for Bob to know when he has actually chosen the right basis and when he has chosen the wrong basis, so his measurement outcome does not contain more information that a random coin-toss.

It is only when the information from Alice (regarding which basis to measure in) has reached him, that he can make use of his earlier (75% erroneous) measurements.

It is in this sence that information cannot propagate faster than the speed of light.

If you are happy with Bob being right only in some percentage of the cases, there is a much easier protocol which does not even require entanglement: Just let Bob guess Alice's bits. He will be right in 50% of the cases.

Note that once the probability to guess the right result is above 50%, communication is possible, e.g. by doing majority voting. In fact, the same is true if Bob gets the correct result with below 50% probability: In that case, he just has to flip every bit, and he will have the correct result with >50% probability.

So regardless of the protocol, what Bob obtains must always be correct with exactly 50% probability, i.e., random.