Do I need a clean install of Lion if I want to defragment my disk?
Mac OS X defragments small files on the go, and has a hot file optimization zone where medium sized and frequently accessed files get ordered on the fast part of a hard drive.

If a tool does a block copy of the drive - fragmentation of files and directories gets moved to the copy destination. When you create a CCC clone, you are not copying the fragmentation state of each file--each file gets written as a single extent on disk. Likewise when you restore from the clone. So if you just wiped and restored from the clone, you'd be starting clean right there.

The apple Disk Utility can be told to do a file level copy or a block level copy - so for a one time copy - it's about as capable as CCC and SuperDuper.

If you're at 95%, it seems to me that a bigger problem is that the operating system can't allocate as much virtual memory as it would want, which would result in a lot of disk thrashing as it constantly clears out the limited VM space it has, which would be consistent with the problems you are reporting. Solution: bigger or emptier hard drive.