Modify base branch and rebase all children at once

Short answer: no, it's not possible ... but you can minimize the amount of work you have to do. Long answer on minimizing work follows.

The key to understanding this is that Git's branch names—the names branch_1, branch_2, and branch_3 in your example—are merely identifiers that "point to" one specific commit. It's the commits themselves that form the actual branches. For details, see What exactly do we mean by "branch"? Meanwhile, what git rebase does is to copy some commits, with the new copies normally being made on a new base (hence "re-base").

In your particular case, there's only one chain of commits that requires copying. That's the B--C--D chain. If we strip off all the labels (branch names) we can draw the graph fragment this way:

A--E
 \
  B--C--D

Your task is to copy B--C--D to B'--C'--D', which are like B through D but come after E instead of coming after A. I'll put them on top so that we can keep the original B--C--D chain in the picture too:

     B'-C'-D'
    /
A--E
 \
  B--C--D

Once you've made the copies, you can then change the labels so that they point to the copies, rather than pointing to the originals; and now we need to move D' up so that we can point branch_2 to C':

          D'   <-- branch_3
         /
     B'-C'     <-- branch_2
    /
A--E           <-- branch_1

This takes a minimum of two Git commands to accomplish:

1. git rebase, to copy B-C-D to B'-C'-D' and move branch_3 to point to D'. Normally this would be two commands:

   git checkout branch_3 && git rebase branch_1
   

   but you can actually do this with one Git command as git rebase has the option of doing the initial git checkout:

   git rebase branch_1 branch_3
   

2. git branch -f, to re-point branch_2.

   We know (from our careful graph drawing that showed us that we could do a single git rebase of branch_3 to copy all the commits) that branch_2 points to the commit "one step back" from the commit to which branch_3 points. That is, at the start, branch_2 names commit C and branch_3 names commit D. Hence, once we're all done, branch_2 needs to name commit C'.

   Since it was one step back from the tip of the old branch_3, it must be one step back from the tip of the new branch_3 afterward.¹ So now that we have done the rebase and have the B'-C'-D' chain, we simply direct Git to move the label branch_2 to point one step back from wherever branch_3 points:

   git branch -f branch_2 branch_3~1
   

Thus, for this case, it takes at least two Git commands (three if you prefer a separate git checkout).

Note that there are cases where more or different commands are required, even if we are moving / copying just two branch names. For instance, if we started with:

F--J        <-- br1
 \
  G--H--K   <-- br2
      \
       I    <-- br3

and wanted to copy all of G-H-(K;I), we cannot do this with one git rebase command. What we can do is rebase either br2 or br3 first, copying three of the four commits; then use git rebase --onto <target> <upstream> <branch> with the remaining branch, to copy the one remaining commit.

(In fact, though, git rebase --onto is the most general form: we can always do the entire job with just a series of git rebase --onto <target> <upstream> <branch> commands, one per branch. This is because git rebase really does two things: (1) copy some set of commits, possibly empty; (2) move a branch label a la git branch -f. The copied set is determined from the result of <upstream>..HEAD—see gitrevisions and footnote 1 below—and with the copy location being set by --onto; and the branch's destination is wherever HEAD winds up after doing the copying. If the to-copy set is empty, HEAD winds up right at the --onto target. So it seems like a simple(ish) script could do all the work ... but see footnote 1.)

---

¹This assumes, however, that git rebase actually winds up copying all the commits. (The safety level of this assumption varies a lot depending on the rebase in question.)

In fact, while the initial set of commits to copy is determined by running git rev-list --no-merges <upstream>..HEAD—or its equivalent, really—that initial set is immediately further whittled-down by computing the git patch-id for each commit in both the "to copy" and "don't need to copy because now will be upstream" ranges. That is, instead of <upstream>..HEAD, the rebase code uses <upstream>...HEAD combined with --right-only --cherry-pick.² So we omit not just merge commits, but also commits that are already upstream.

We could write a script that does this ourselves, so that we can locate the relative position of each branch-name in the set of branches we wish to rebase. (I did most of this as an experiment some time ago.) But there is another problem: during the cherry-picking process, it's possible that some commits will become empty due to conflict resolution, and you will git rebase --skip them. This changes the relative position of the remaining copied commits.

What this means in the end is that unless git rebase is augmented a bit, to record which commits map to which new commits and which commits were dropped entirely, it's impossible to make a completely-correct, completely-reliable multi-rebase script. I think one could get sufficiently close, without modifying Git itself, using the HEAD reflog: this would only go awry if someone starts this kind of complex rebase, but then in the middle of it, does some git reset --softs and the like and then resumes the rebase.

²This is literally true for some forms of git rebase and not for others. The code to generate the list varies depends on whether you're using --interactive and/or --keep-empty and/or --preserve-merges. A non-interactive git am based rebase uses:

if test -n "$keep_empty"
then
    # we have to do this the hard way.  git format-patch completely squashes
    # empty commits and even if it didn't the format doesn't really lend
    # itself well to recording empty patches.  fortunately, cherry-pick
    # makes this easy
    git cherry-pick ${gpg_sign_opt:+"$gpg_sign_opt"} --allow-empty \
        --right-only "$revisions" \
        ${restrict_revision+^$restrict_revision}
    ret=$?
else
    rm -f "$GIT_DIR/rebased-patches"

    git format-patch -k --stdout --full-index --cherry-pick --right-only \
        --src-prefix=a/ --dst-prefix=b/ --no-renames --no-cover-letter \
        "$revisions" ${restrict_revision+^$restrict_revision} \
        >"$GIT_DIR/rebased-patches"
    ret=$?

[snip]

    git am $git_am_opt --rebasing --resolvemsg="$resolvemsg" \
        ${gpg_sign_opt:+"$gpg_sign_opt"} <"$GIT_DIR/rebased-patches"
    ret=$?

[snip]

The --cherry-pick --right-only are passed through whichever command is used (cherry-pick or format-patch) to the git rev-list code, so that it can get the right-hand-side list of commit IDs, with "pre-picked cherries" removed, from the symmetric difference.

Interactive rebase is considerably more complicated (!).