Proof of Cauchy's mean value theorem and Lagrange's mean value theorem that does not depend on Rolle's theorem

If you have somehow proved Cauchy's theorem, you have as a bonus also Rolle's and Lagrange's. Conversely, Rolle's theorem easily implies Cauchy's, via an affine transformation. Thus the three theorems are equivalent to one another. Proving one is the same as proving all three of them.

Rolle's theorem for $f$ continuous on $[a,b]$ and differentiable in $(a,b)$ states the existence of an internal critical point for the function $f$. I don't think there's a way for proving such existence without using the fact that a continuous function on a closed and bounded interval has maximum and minimum.

Even if we assume the derivative is continuous on $(a,b)$ we cannot appeal to the fact that $f$ is monotonic if the derivative doesn't vanish, because this follows from Lagrange's theorem.