#すぐさま rbenv-gem-rehash を入れよう
Qiita で「rbenv を使って Ruby をインストールした」記事は 毎日1回以上 あります。にも関わらず、そのほとんどが「Rails などをインストールしたら rbenv rehash します」と書いている。
なぜ rbenv-gem-rehash を入れないんだ。

Never run rbenv rehash again. This rbenv plugin automatically runs rbenv rehash every time you install or uninstall a gem.
もう二度と rbenv rehash しなくていい。 gem をインストール/アンインストールする度に、この rbenv プラグインが自動的に rbenv rehash する。
sstephenson/rbenv-gem-rehash

#インストール
もちろん rbenv インストール済みとします。
##Mac以外

$ git clone https://github.com/sstephenson/rbenv-gem-rehash.git ~/.rbenv/plugins/rbenv-gem-rehash

##Mac で Homebrew を使って rbenv をインストールした場合

$ brew install rbenv-gem-rehash

#もう rbenv rehash を忘れても良いんだ！
忘れちまえ！

2014/12/25追記：

この Pull Request で rbenv-gem-rehash プラグインが不要になったとの投稿もみました（状況未確認）。