How can I rebase multiple branches at once?

You can't get this in one step. At best you move each branch one by one; this would be the sequence:

git rebase --onto master exp1
git rebase --onto c2' c2 exp2
git rebase --onto c1' c1 exp3
git rebase --onto master exp4

The key is to rebase from each branch point in the old tree (e.g. c2 in the above) on to the new tree (e.g. c2' in the above).

I just want to mention that GoZoner's sequence has a mistake in the first (and last) line. exp1 is not the upstream, but the branch you want to rebase.

In order to start the sequence, you need to have master as upstream, i.e. git rebase --onto master master exp1 or short, without --onto it would be git rebase master exp1. The total correct sequence for the example from the question would then be:

git rebase master exp1
git rebase --onto c2' c2 exp2
git rebase --onto c1' c1 exp3
git rebase master exp4

As GoZoner answered, there's no way of doing this using the bare git commands, but it's doable to support this kind of rebasing through a script that combines various git plumbing commands.

I wrote a working example, you can find it on github

You can rebase multiple branches / trees with a small trick.

1. Create a DUMMY_BRANCH e.g. at location of master
2. Merge all branches you like to move into DUMMY_BRANCH (Using a --no-ff Merge) - Update for comments from @kdb, @franckspike
3. rebase DUMMY_BRANCH to your desired new point and add --preserve-merges option to your rebase-command
4. After rebasing manually each of you branches to the rebased commits (e.g. for C4 git reset --hard [Commit-hash of C4' (exp1)]
5. when you have moved all your branches, delete the rebased DUMMY_BRANCH