Fan is weird, really weird

Fan sounds like the wind blowing in a B-rated 60s movie. Starts, stops, whirls, pauses, then starts again, runs for a while, stops for a few minutes, repeat cycle. CPU load doesn’t seem to have any connection to the behaviour.

So I replaced the fan and clean installed OSX - with no change. I also tried to monitor the fan and temp using a few of the available apps, and none of them seem to be able to read the RPM - it says 0 although that is clearly wrong. So it’s clearly a hardware issue, though not the fan itself.

What diagnostics could I try?