I'm experiencing KDE freezes all the time.

For example, I click on an icon on the taskbar and it reacts (activates the window) after a minute.

Otherwise my system is performing well, if I switch tasks using alt-tab it works instantly. System load is low, there's now iowait (ssd), plenty of free RAM. I did not remove akonadi/nepomuk yet, but they don't seem to use too much CPU.

If I click on anything on the desktop or taskbar, I sometimes wait for a minute. I already removed all plasmoids from the desktop because I suspected they may be slow.

My question is: How do I debug it? Are there any tools to examine in which part of code KDE spends time? If KDE was a multi-process system I'd use top but it won't really help me tell which part of Plasma is taking too much time.

I'm not looking for help with my particular system, I'm looking for a general way to solve KDE performance problems.

Unfortunately there is no "general" way to solve "problems" as they depend on the specifics of the problem at hand.
In your case I strongly suspect you're using a proprietary driver - likely Nvidia?

No, I'm using an Intel chipset running on i915 kmod.

It may be as well an issue of the video drivers: what distribution are you using? One of my machines runs 4.13 beta (a rather slow dual core netbook with i915) and I've yet to see any freeze.

I highly doubt it's a video driver issue, everything but KDE works quickly (even Kwin, if I don't use the taskbar or desktop, the animations are smooth)

It wasn't like this out of the box, it could be some change I made, but I need a way to find out what's going on other than rm -rf ~/.kde4

Linux Mint 15 Olivia

What form of Intel graphics are you running? Depending on the version of the driver you're using, and the parameters it is set to use (which some distributions could be patching to enable) the Intel driver can be unstable.

To eliminate any form of KDE related configuration, please try a new user.

As for why it appears to perform extremely well, but then freeze - the driver could be inducing a deadlock within the GPU, which then causes the GPU to be reset - which would explain why the issue corrects itself.

I just went the other route - tried running KDE over VNC, same user, same configuration. It freezes.

As requested - please try a new user account to eliminate any configuration related causes.
Also, please perform an exact timing of the freeze.

Finally, how did you access it via VNC? Depending on how it was done, the system may still have been using the primary GPU - exposing you to the same cause of the freeze.