You want to use the --follow option on git log, which is described in the man page as:
Continue listing the history of a file beyond renames.
Effectively, not only does this allow you to see the history of a renamed file, but this also allows you to view the history of a file no longer in the working tree. So the command you should use should look something like:
git log --follow -- foo
Update:
Git 2.9+ has now enabled this by default for all git diff and git log commands:
The end-user facing Porcelain level commands in the “git diff” and
“git log” family by default enable the rename detection; you can still
use “diff.renames” configuration variable to disable this.
Thanks to x-yuri for the heads up!