That's a good point, if we create the usual structure, we regard entropy as a more advanced concept than anything that appears in the zeroth law. The zeroth law only refers to heat exhange, and asserts that the absence of spontaneous heat exchange is a transitive relationship. By mentioning temperature, Feynman got us thinking in terms of the second law, but if one sticks to the structure you have in mind, we should note as you say that the concept of temperature is made possible by the zeroth law. So we should be asking, what makes the concept of temperature possible?
Personally, I think all of thermodynamics starts with entropy, so the zeroth law should be about entropy, so should be something like, "what happens spontaneously is what increases entropy," which we normally think of as the second law. The next crucial concept is heat, so the first law should be something like the transitive relationship between systems that won't spontaneously exchange heat, which is what we now think of as the zeroth law. This law would stem from the fact that if sending heat from system 1 to 3 will increase entropy, then sending heat from 1 to 2 and from 2 to 3 should also increase entropy, so should not be disallowed even if system 3 is only connected to system 1 via system 2 (which is pretty much the proof that JDStupi referred to using T, but T is not needed for that proof). Then we need to bring in the other types of energy, in the second law (which was the first). We never need the previous second law, because it stems from the zeroth law, and our definition of T need not be viewed as a law, just a handy way to define the key parameter that describes these equilibrium classes. So I am a proponent of inserting the second law ahead of the zeroth law.