No, the proof doesn't need an expected running time. The running time T(N) is expressed as:

T(N) = T(N/5) + T(7N/10 + 10) + Ο(N);

which has T(N) = Ο(N) as a solution.

However I believe it will be much harder to prove that the push is O(1) - indeed I suspect it is not - and without that the algorithm as a whole cannot be O(n).

It doesn't have to be. What's needed is that the push has an amortized running time of Ο(1) - that is, if we perform N pushes, the total running time is still bounded by Ο(N). And from what I understand of how allocation of array sizes work (an addition extra 20% memory is being claimed), a push has an amortized Ο(1) performance. A single push may take Θ(N) running time, but N pushes average it out.