I'm someone who has started enjoying rebasing workflow after using branch-merge workflow for more than a decade. So perhaps, my experience may be useful since you can compare the same person using both of them. The first thing to realize is that branch-merge and rebase workflows try to achieve different goals. Branch-merge tries to preserve history of the code, with every wart and quirk included. Rebase tries to achieve a clean history where every commit is an entire fully functional (without known errors) feature with complete explanation in the commit message. People fight over them, but I find both goals to be meaningful and the choice depends on your priorities. In fact, I do both- publish a clean history in the master and the original messy history as a separate branch.
> I'd really like to know what mess people make when they don't rebase.
As a developer, we have the expectation that git will allow us to experiment with features, make mistakes, correct them, roll them back and improve. That stage is also so messy that you'd leave short commit messages that would make sense only to you. This is fine while developing. But this leaves many commits that are functionally broken, partial or rolled back later. That, along with vague commit messages and illogical commit order make it really hard for someone else to pick up a working commit from your branch and continue. Heck! I find it hard to choose a commit even from my own older repositories. That isn't the case with good projects like the kernel. You can pick any commit on the master and it will compile and work with all the features advertised up to that commit message. It makes a users' life easier.
> I've found that using merge gives a readable trail of when something was merged, whether that be from a branch's original branch, or if you're merging into another branch.
This is true. It's harder to achieve with rebasing. But it's possible with some work. I usually leave the original messy feature branch intact, and mark the rebased HEAD with a similar-worded tag or branch.
> Rebasing just seems to cause a lot more headache when something doesn't go perfectly correct in between commits.
Don't take any offense, but those are beginner blues. It happens in the early stage of learning rebases when you don't have a full grasp of what is going on. People evolve different strategies to overcome this once they are a bit more comfortable. My strategy is to create a temporary branch for rebasing (at the same commit as the feature branch) and do multiple rebases on it. I do only one or maximum two operations during each rebase. The result of each rebase is reviewed before doing the next round of rebase on the same branch. The original feature branch is left intact in case something goes wrong - though I never needed it.
Other people do rebasing occasionally while developing the branch. They do this after every two or three commits. They end up with a clean history to merge (fast-forward) to master, by the time they finish the branch. All of these operations can be simplified using helper tools like git-revise [1].
My absolute favourite method is to not use rebase at all. Craft the perfect commits as you develop. This can be achieved with a patch stack tool like quilt or stacked-git [2]. It allows you to move your changes to a patch (commit) of your choice. This is like having multiple staging indexes available. You can also split, combine or reorder patches. The patch stack evolves as you develop, but you end up with a perfect history to merge (fast-forward) at the end.
[1] https://github.com/mystor/git-revise/
[2] https://stacked-git.github.io/