Since homebrew does not officially support an automated way to do that, I created a small zsh function to remove a formula and all its dependencies.

I use zsh on the Mac so the function works with it. Feel free to adjust it if you are using bash or something else.

brew-remove-with-deps() {
  formula="$*"

  if [ "x$formula" = "x" ]
  then
     echo "Invalid empty parameter"
  else
     echo "Removing" "$formula" "and all its deps.."
     brew rm $formula
     brew rm $(join <(brew leaves) <(brew deps "$formula"))
  fi
}

And, just for testing purposes:

elbryan@snowbox ~ % brew-remove-with-deps sloccount
Removing sloccount and all its deps..
Uninstalling /usr/local/Cellar/sloccount/2.26...
Uninstalling /usr/local/Cellar/md5sha1sum/0.9.5...

Et voilà.

References:
[1] – Stackoverflow – Uninstall / remove a Homebrew package including all its dependencies