It might not be possible to do it with an interpreter, but a well-designed JIT should be able to shift the cost of calculating instruction scheduling and cycle-costs from execution time to JIT time.
Since OoO CPUs spend long stretches of time between branch miss-predicts and L1 cache misses, you can get long sequence of instructions that executing with the exact same timings every time. A tracing JIT is perfect for this usecase. You just need to normalise the pipeline state on entry (and this since this normally happens after a miss-predict, the pipeline is often drained), and then exit on every branch miss-predict or L1 cache miss and start a new trace.
I suspect such a scheme might be fast enough for a Pentium III, I just need to find some time to actually try out my ideas at some point.