My idea was to carry a variable that is initially seeded with the input to the algorithm. Then, with a yet-to-be-defined distribution random operations are added in between the lines of the original PoW function that perform changes to that new variable (here, it could frequently mix in the state in some form). As you pointed out, this boils down to creating some level of overhead that a faster-algorithm attacker needs to additionally perform to his handcrafted PoW function.
This is close enough to my scheme that I may as well just spell it out.
Declare a buffer of length L. L is a network wide (and possibly varying) parameter and is the deterministic proxy for time. "After 10ms" means deterministically "when the buffer is full".
As each executable statement is executed, write to the buffer the statement number followed by the list of variable assignments effected by that statement. So for example, if in the C language, statement 100 was
(I don't know if you can do that in python), and if before the statement was executed c=3 and d=4, then you would write to the buffer
And write all of this, even if b was already equal to 7, so was not changed (but could have been). c can not have changed so doesn't need to be written.
I would argue that to write that buffer is by definition to run the program. What does "running a program" even mean, if not to determine the sequence of changes to state defined by its statements? If "work" means "runs the program" than I cannot think of a definition of the phrase "proof of work" that is not satisfied by writing that buffer. Yet still an adversary could craft a program that writes the buffer in a way that he can predict using a faster algorithm.
But lets not worry about that now. Instead, let me continue with my idea. I claim that the buffer will be written at a more or less constant rate. In general, statements which change more variables will also take proportionately longer to execute. If necessary we could add padding for statements that take much longer than average to execute.
Next note that SHA-256 is a serial algorithm. We don't even need to allocate storage for the buffer; we just pipe it straight in. Finally, note that it is a linear-time algorithm. Any new algorithm computing the same function can be at best a constant times faster, otherwise finding collisions becomes trivial. This is the basis for my claim that even the most powerful faster algorithm imaginable - an oracle that fills the buffer instantly - can achieve at best a linear speed-up.
Finally let's take a look at how your idea fits into this:
My idea was to carry a variable that is initially seeded with the input to the algorithm. Then, with a yet-to-be-defined distribution random operations are added in between the lines of the original PoW function that perform changes to that new variable (here, it could frequently mix in the state in some form).
This is equivalent to encrypting the buffer using the seed as a key. I have also had this idea. It adds overhead that the adversary cannot avoid, but no more security because the attacker knows the key. It's like DRM when the attacker is in the box.