Definitely yes, you have to root first. Install one of the various ROMs, and then use SetCPU.
I've done this on my wife's phone that I rooted. I'm on leak v3 so I can't root yet...
I'm using Ivans Rom version 1, she's clocked up to around 712mghz. Ivan is working on an undervolted version which will allow it to continue at current speeds, and overclocked but use less power(more batter time for us).
Check the Rooted section for details.