This useful tip is taken from the article Uninstalling brew (so I can reinstall)
WARNING: Before copying and pasting these commands on your shell, make sure the first one (`brew --prefix`) returns the path where homebrew was installed properly. If not, you might ending up removing stuff from your computer you did not intend to remove.
cd `brew --prefix`
rm -rf Cellar
brew prune
rm -rf Library .git .gitignore bin/brew README.md share/man/man1/brew
rm -rf ~/Library/Caches/Homebrew
ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go)"