EDIT: wnoise's suggestion will work if you don't want to keep an explicit history the way pushd/popd does. If you do (and don't want an ordinary checkout to affect your LRU):
I don't know of anything that will do what you want out of the box, but it's not to hard to hack together something along those lines. If you add a file named git-foo to your PATH, you get a new git foo command. So, git-pushd could look like:
#!/bin/bash
SUBDIRECTORY_OK=1
. $(git --exec-path)/git-sh-setup
git symbolic-ref HEAD | sed s_refs/heads/__ >> $GIT_DIR/.pushd
git checkout "$@"
And git-popd:
#!/bin/bash
SUBDIRECTORY_OK=1
. $(git --exec-path)/git-sh-setup
REF=$(head -n1 $GIT_DIR/.pushd)
[ -n "$REF" ] || die "No refs to pop"
git checkout "$REF" && sed -i -e '1d' $GIT_DIR/.pushd