Is it possible to make a proof of work scheme where you can prove how many iterations you have done without (*the verifier*) redoing the whole calculation?

Yes, with a number of conditions.

First, we need "iterations" which can be done in parallel:

E.g.

for i in 0..10: output[i] = pow(i)

instead of:

output[i] = pow(output[i-1])

Given that, say we're going to do 65536 iterations.

for i 0..65535:

output[i] = pow(i)

Now arrange the output_i into the leafs of a fully populated binary tree. It will have a depth of 16 levels for 65536 iterations. At each node in the tree hash its children... just like a transaction hash tree in Bitcoin.

Take the first ~128 bits of the root hash and use as indexes to pick eight unique iteration outputs.

Collect those outputs along with the tree fragments that connect them up to the root.

Your proof of work is the eight solutions and the connecting tree fragments. This demonstrates with high probability that all the work was actually done— an attacker who only did eight of the iterations then searched for a random value that specified his 8 would have to do 2^128 work. You can twiddle the numbers for a bandwidth/security tradeoff.

This is called non-interactive cut and choose and it's often used in various kinds of zero knowledge proof.

If you were specifically wanting a _serial_ proof of work— then no, one can't be constructed. Unless you make everyone work on the same problem (and then its a race, which _bad_) anyone can use the randomization to convert an arbitrarily serial POW into a fully parallel one.