Delete all wallet addresses
Transfer all funds out of the old wallet.
If on Windows, explore to %APPDATA%\Bitcoin, rename wallet.dat to wallet-old.dat.
On next launch of Bitcoin-QT a new, empty wallet.dat will be created. 
This will not require re-downloading the blockchain.
Remember to use Settings, Encrypt Wallet on the new wallet.dat.