Don't hide functionality in shortcuts.
If your user's work flow demands the need to quickly and easily deselect all options, make the option explicit. Provide a button that does what it says:
download bmml source – Wireframes created with Balsamiq Mockups
Now it is clear to the user how to deselect everything they've selected. A click of the button and a click of "Option 3" gives them what they want. Easily.
Don't confuse system shortcuts
Shift-click has meaning in many systems and when dealing with lists. It will, often, select (or de-select) all items between the last selection and the item just clicked. Don't redefine a user's mental model of how that shortcut works.