When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing requires massively parallel processing, but they argue that things like DOOM were done on single-core CPUs without GPUs.

Is there anything that must be done on a multi-core processor?

Assume there is infinite time for both development and running.

If you don't care about the running time, anything you can do on a multi-core machine, you can do on a single-core machine.  A multi-core machine is just a way of speeding up some kinds of computations.

If you can solve a problem in time $T$ on a multi-core machine with $n$ cores, then you can solve it time $\sim Tn$ (or less look at Amdahl's law) on a single-core machine.  The single-core machine can emulate a multi-core machine using time-slicing / time-sharing.
