This is not entirely true. Or rather: it is true when the countermeasure is to add random delays to pad out overall timing, since one can simply collect more samples to obtain an average. And that may be what the OP is suggesting: just scale the frequency to random levels that are not quite the pre-programmed ones, which is very similar to adding random delays. (In practice this might actually work well enough to defeat delicate attacks.) However what I hoped the OP was suggesting is to add random instructions as a way to prevent the processor from switching power modes: sort of like tapping your phone screen occasionally to keep it from dimming.

There are also other (unrelated) techniques that use randomness to eliminate side channels. One of the most basic anti-timing-attack countermeasures is to use RSA blinding in which a base C is first randomized by computing C^r mod N before that (random) result is combined with the secret key. The randomness can then be removed from the final result. This defeats attacks that depend on choosing or knowing the value C.

Does that necessarily mean that all is lost? It sounds possible to arbitrarily extend the time necessary. Don't we already do this when we choose encryption keys with lengths that take an arbitrary amount of time to crack by brute force?

100% correct

What if you discretized the allowed frequencies and linked the rate at which the cpu could switch?

Except that the processor can be doing other work during artificially induced noise delays, something not possible with delays introduced by lower mean frequency.

An additional millisecond to your public key exchange is probably not going to matter - key exchange is pretty infrequent anyway.

The attack isn't nicely asking the computer "hey how fast are you running right now?" and then deriving the private key from that data. If that was the case the fix would be as simple as you laid out here.

This attack works by measuring the absolute (wall) time that elapses during many crypto operations and deriving the speed / private keys based on statistical methods applied to that timing data.

Side-channel attacks are by definition, attacks against unintentional information leakage by a machine. The laws of thermodynamics virtually ensure that side channel attacks will be a persistent issue as long as computers are made of matter and consume electricity, multi-tenant computing exacerbates the issue.