Is there anything I don't have to install? I have Partition Magic cd here, but don't want to mess my clean install with crapload of other stuff. Is there any utility that would be able to shrink current partition and let me create new, small one?

Partition Magic has the ability to create a bootable CD or floppy disk set. That way you can boot into Partition Magic and it doesn't have to be on the Hard Drive.

That's good idea. BUT wouldn't that screw the data on it somehow? I mean that's DOS mode afaik... If I was to do stuff like that, I'd rather do it from Windows.

It's always going to be iffy, operating on the partition you're running your system from.

Much better far to use a tool which doesn't require it - I recently tried copying combined with size change of partitions size (to a new HDD) using PM, and it screwed something up - so I did the job with Acronis TrueImage and not such a messing about with sizes. If things can get messed up when not even changing the partition you're running from, think how much worse it might be!

Do do a proper partition image to somewhere 'external' just in case.

I think to do it again I'd be looking to use gparted and use the gparted CD

I finally solved it by "borrowing" a HDD from one PC at work. The joy of working as IT support