How do you fix a bad merge, and replay your good commits onto a fixed merge?

Please don't use this recipe if your situation is not the one described in the question. This recipe is for fixing a bad merge, and replaying your good commits onto a fixed merge.

Although filter-branch will do what you want, it is quite a complex command and I would probably choose to do this with git rebase. It's probably a personal preference. filter-branch can do it in a single, slightly more complex command, whereas the rebase solution is performing the equivalent logical operations one step at a time.

Try the following recipe:

# create and check out a temporary branch at the location of the bad merge
git checkout -b tmpfix <sha1-of-merge>

# remove the incorrectly added file
git rm somefile.orig

# commit the amended merge
git commit --amend

# go back to the master branch
git checkout master

# replant the master branch onto the corrected merge
git rebase tmpfix

# delete the temporary branch
git branch -d tmpfix

(Note that you don't actually need a temporary branch, you can do this with a 'detached HEAD', but you need to take a note of the commit id generated by the git commit --amend step to supply to the git rebase command rather than using the temporary branch name.)

Intro: You Have 5 Solutions Available

The original poster states:

I accidentally committed an unwanted file...to my repository several commits ago...I want to completely delete the file from the repository history.

Is it possible to rewrite the change history such that filename.orig was never added to the repository in the first place?

There are many different ways to remove the history of a file completely from git:

Amending commits.
Hard resets (possibly plus a rebase).
Non-interactive rebase.
Interactive rebases.
Filtering branches.

In the case of the original poster, amending the commit isn't really an option by itself, since he made several additional commits afterwards, but for the sake of completeness, I will also explain how to do it, for anyone else who justs wants to amend their previous commit.

Note that all of these solutions involve altering/re-writing history/commits in one way another, so anyone with old copies of the commits will have to do extra work to re-sync their history with the new history.

Solution 1: Amending Commits

If you accidentally made a change (such as adding a file) in your previous commit, and you don't want the history of that change to exist anymore, then you can simply amend the previous commit to remove the file from it:

git rm <file>
git commit --amend --no-edit

Solution 2: Hard Reset (Possibly Plus a Rebase)

Like solution #1, if you just want to get rid of your previous commit, then you also have the option of simply doing a hard reset to its parent:

git reset --hard HEAD^

That command will hard-reset your branch to the previous 1^st parent commit.

However, if, like the original poster, you've made several commits after the commit you want to undo the change to, you can still use hard resets to modify it, but doing so also involves using a rebase. Here are the steps that you can use to amend a commit further back in history:

# Create a new branch at the commit you want to amend
git checkout -b temp <commit>

# Amend the commit
git rm <file>
git commit --amend --no-edit

# Rebase your previous branch onto this new commit, starting from the old-commit
git rebase --preserve-merges --onto temp <old-commit> master

# Verify your changes
git diff master@{1}

Solution 3: Non-interactive Rebase

This will work if you just want to remove a commit from history entirely:

# Create a new branch at the parent-commit of the commit that you want to remove
git branch temp <parent-commit>

# Rebase onto the parent-commit, starting from the commit-to-remove
git rebase --preserve-merges --onto temp <commit-to-remove> master

# Or use `-p` insteda of the longer `--preserve-merges`
git rebase -p --onto temp <commit-to-remove> master

# Verify your changes
git diff master@{1}

Solution 4: Interactive Rebases

This solution will allow you to accomplish the same things as solutions #2 and #3, i.e. modify or remove commits further back in history than your immediately previous commit, so which solution you choose to use is sort of up to you. Interactive rebases are not well-suited to rebasing hundreds of commits, for performance reasons, so I would use non-interactive rebases or the filter branch solution (see below) in those sort of situations.

To begin the interactive rebase, use the following:

git rebase --interactive <commit-to-amend-or-remove>~

# Or `-i` instead of the longer `--interactive`
git rebase -i <commit-to-amend-or-remove>~

This will cause git to rewind the commit history back to the parent of the commit that you want to modify or remove. It will then present you a list of the rewound commits in reverse order in whatever editor git is set to use (this is Vim by default):

pick 00ddaac Add symlinks for executables
pick 03fa071 Set `push.default` to `simple`
pick 7668f34 Modify Bash config to use Homebrew recommended PATH
pick 475593a Add global .gitignore file for OS X
pick 1b7f496 Add alias for Dr Java to Bash config (OS X)

The commit that you want to modify or remove will be at the top of this list. To remove it, simply delete its line in the list. Otherwise, replace "pick" with "edit" on the 1^st line, like so:

edit 00ddaac Add symlinks for executables
pick 03fa071 Set `push.default` to `simple`

Next, enter git rebase --continue. If you chose to remove the commit entirely, then that it all you need to do (other than verification, see final step for this solution). If, on the other hand, you wanted to modify the commit, then git will reapply the commit and then pause the rebase.

Stopped at 00ddaacab0a85d9989217dd9fe9e1b317ed069ac... Add symlinks
You can amend the commit now, with

        git commit --amend

Once you are satisfied with your changes, run

        git rebase --continue

At this point, you can remove the file and amend the commit, then continue the rebase:

git rm <file>
git commit --amend --no-edit
git rebase --continue

That's it. As a final step, whether you modified the commit or removed it completely, it's always a good idea to verify that no other unexpected changes were made to your branch by diffing it with its state before the rebase:

git diff master@{1}

Solution 5: Filtering Branches

Finally, this solution is best if you want to completely wipe out all traces of a file's existence from history, and none of the other solutions are quite up to the task.

git filter-branch --index-filter \
'git rm --cached --ignore-unmatch <file>'

That will remove <file> from all commits, starting from the root commit. If instead you just want to rewrite the commit range HEAD~5..HEAD, then you can pass that as an additional argument to filter-branch, as pointed out in this answer:

git filter-branch --index-filter \
'git rm --cached --ignore-unmatch <file>' HEAD~5..HEAD

Again, after the filter-branch is complete, it's usually a good idea to verify that there are no other unexpected changes by diffing your branch with its previous state before the filtering operation:

git diff master@{1}

Filter-Branch Alternative: BFG Repo Cleaner

I've heard that the BFG Repo Cleaner tool runs faster than git filter-branch, so you might want to check that out as an option too. It's even mentioned officially in the filter-branch documentation as a viable alternative:

git-filter-branch allows you to make complex shell-scripted rewrites of your Git history, but you probably don’t need this flexibility if you’re simply removing unwanted data like large files or passwords. For those operations you may want to consider The BFG Repo-Cleaner, a JVM-based alternative to git-filter-branch, typically at least 10-50x faster for those use-cases, and with quite different characteristics:

Any particular version of a file is cleaned exactly once. The BFG, unlike git-filter-branch, does not give you the opportunity to handle a file differently based on where or when it was committed within your history. This constraint gives the core performance benefit of The BFG, and is well-suited to the task of cleansing bad data - you don’t care where the bad data is, you just want it gone.

By default The BFG takes full advantage of multi-core machines, cleansing commit file-trees in parallel. git-filter-branch cleans commits sequentially (ie in a single-threaded manner), though it is possible to write filters that include their own parallellism, in the scripts executed against each commit.

The command options are much more restrictive than git-filter branch, and dedicated just to the tasks of removing unwanted data- e.g: --strip-blobs-bigger-than 1M.

Additional Resources

Pro Git § 6.4 Git Tools - Rewriting History.
git-filter-branch(1) Manual Page.
git-commit(1) Manual Page.
git-reset(1) Manual Page.
git-rebase(1) Manual Page.
The BFG Repo Cleaner (see also this answer from the creator himself).