状況

新しく買ったPCでbrewをインストールした
iterm2をインストールした。
zshをインストールした
ログインシェルをzshにした
iterm2でbrewコマンドが使えない！ <= いまココ

原因

/usr/local/bin にパスが通っていないことが原因。
今回ダウンロードしたbrewコマンドは、/usr/local/bin/brewに保存されていたため、/usr/local/binにパスが通っていないとbrewコマンドが使えなかった。
（「パスを通す」という事の意味が初めて理解できた気がする。@soarflatさん感謝です。）

解決方法

terminal側（brewがうまく使える側）でecho $PATHを実行。すると通っているPATHが確認できるので（僕の場合は「/usr/bin:/bin:/usr/sbin:/sbin」）、それをexportコマンドの引数にして~/.zshrcにコピペ(export PATH="/usr/local/bin:/usr/local/sbin:$PATH")。そしてitermを再起動するとbrewコマンドが使える。順に書くと

echo $PATH
1の結果を~/.zshrcにコピーしておく
.zshrcファイルを開く(vim ~/.zshrc)
1の結果をexportコマンドの引数としてコピペ（export PATH="/usr/local/bin:/usr/local/sbin:$PATH"）
itermを再起動

参考

zshにしたらbrewコマンドもvagrantコマンドも使えなくなった時の対処法
https://taccuma.com/brew-and-vagrant-command-not-found-in-zsh/
PATHを通すとは？ (Mac OS X)
http://qiita.com/soarflat/items/09be6ab9cd91d366bf71