How do I Re-root a git repo to a parent folder while preserving history?

Rather than create a new repository, move what's in your current repository into the right place: create a new directory bar in your current directory and move the current content in (so your code is in /foo/bar/bar). Then create a baz directory next to your new bar directory (/foo/bar/baz). mv /foo /foo2; mv /foo2/bar /foo; rmdir /foo2 and you're done :).

Git's rename tracking means that your history will still work and Git's hashing of content means that even though you've moved things around, you're still referencing the same objects in the repository.

What you want is git filter-branch, which can move a whole repository into a subtree, preserving history by making it look as if it's always been that way. Back up your repository before using this!

Here's the magic. In /foo/bar, run:

git filter-branch --commit-filter '
    TREE="$1";
    shift;
    SUBTREE=`echo -e 040000 tree $TREE"\tbar" | git mktree`
    git commit-tree $SUBTREE "$@"' -- --all

That will make the /foo/bar repository have another 'bar' subdirectory with all its contents throughout its whole history. Then you can move the entire repo up to the foo level and add baz code to it.

Update:

Okay, here's what's going on. A commit is a link to a "tree" (think of it as a SHA representing a whole filesystem subdirectory's contents) plus some "parent" SHA's and some metadata link author/message/etc. The git commit-tree command is the low-level bit that wraps all this together. The parameter to --commit-filter gets treated as a shell function and run in place of git commit-tree during the filter process, and has to act like it.

What I'm doing is taking the first parameter, the original tree to commit, and building a new "tree object" that says it's in a subfolder via git mktree, another low-level git command. To do that, I have to pipe into it something that looks like a git tree i.e. a set of (mode SP type SP SHA TAB filename) lines; thus the echo command. The output of mktree is then substituted for the first parameter when I chain to the real commit-tree; "$@" is a way to pass all the other parameters intact, having stripped the first off with shift. See git help mktree and git help commit-tree for info.

So, if you need multiple levels, you have to nest a few extra levels of tree objects (this isn't tested but is the general idea):

git filter-branch --commit-filter '
    TREE="$1"
    shift
    SUBTREE1=`echo -e 040000 tree $TREE"\tbar" | git mktree`
    SUBTREE2=`echo -e 040000 tree $SUBTREE1"\tb" | git mktree`
    SUBTREE3=`echo -e 040000 tree $SUBTREE2"\ta" | git mktree`
    git commit-tree $SUBTREE3 "$@"' -- --all

That should shift the real contents down into a/b/bar (note the reversed order).

Update: Integrated improvements From Matthew Alpert's answer below. Without -- --all this only works on the currently-checked out branch, but since the question is asking about a whole repo, it makes more sense to do it this way than branch-by-branch.