There are a number of good answers already, but some are out of date and none of them are entirely complete. In particular, most of them will remove dependencies but still leave it up to you to remove the originally-targeted formula afterwards. The posted one-liners can also be tedious to work with if you want to uninstall more than one formula at a time.
Here is a Bourne-compatible shell function (without any known Bashisms) that takes a list of formulae, removes each one's dependencies, removes all copies of the formula itself, and then reinstalls any missing dependencies.
unbrew () {
local formula
for formula in "$@"; do
brew deps "$formula" |
xargs brew uninstall --ignore-dependencies --force
brew uninstall --force "$formula"
done
brew missing | cut -f2 -d: | sort -u | xargs brew install
}
It was tested on Homebrew 1.7.4.
This works on all standard formulae that I tested. It does not presently handle casks, but neither will it complain loudly if you attempt to unbrew a cask with the same name as a standard formula (e.g. MacVim).