History is only "cleaner" because Git in its default configuration only throws the raw version graph at you and fails to visualize it in a readable fashion. With a properly structured visualization, such as Bazaar's hierarchical logs, merging is not just as clean, it actually carries more information.
In hierarchical logs, a merge commit stands for the series of commits that are being merged. You can then unfold such commits and view the series of commits as a nested list of commits (which may again contain merge commits).
Think of a merge commit as the equivalent of a procedure call where the procedure body is the series of commits being merged.
(Note that there are other ways to visualize version graphs with merge commits; this is just the simplest way to do it and could actually be easily added on top of Git.)
Rebasing has two problems. It discards the original version structure and it can create commits that never build or don't pass tests (because they never existed as such).
Frequent use of rebasing is almost always an indication that a VCS is lacking important functionality.