So, when rebasing, choose to edit both the commit where you added the file by mistake, and the one you want to add it to in that order. If the file is in a later commit, but should be in an earlier one, you will have to reorder the lines. For example, I start with
pick 8de731b Commit with missing file.
pick bbef925 Commit with too many files.
pick 52490ce More history.
I need to change it to
edit bbef925 Commit with too many files.
edit 8de731b Commit with missing file.
pick 52490ce More history.
Then,
# In the commit containing an extra file
git reset HEAD^ badfile.c
git commit --amend
git rebase --continue
# Now in the commit to add it to
git add badfile.c
git commit --amend
git rebase --continue
Unfortunately, when editing history in one branch, I don't know of any way to avoid editing history in all branches. Rebasing should be done as early as possible to avoid problems like this. In my simple case here, I can merge master and the other branch, but the commits don't merge, then I have to rebase in master, and reorder and squash the commits, like this:
pick 7cd915f Commit with missing file.
fixup 8de731b Commit with missing file. #This was the higher of the two entries
pick 8b92c5a Commit with too many files.
fixup bbef925 Commit with too many files. #This was the higher of the two entries
pick 94c3f7f More history.
fixup 52490ce More history. #This was the higher of the two entries
Late edit: I just noticed I was accidentally reordering the commit history as a carryover from my original answer. Swapping the lines in the rebase changes the order you commit; after editing, you can rebase again and swap them back to go back to the original commit order.