This is superior to the rebase solution because it preserves committer info, committer dates, and non-empty merges of the original history.
git filter-branch --prune-empty --parent-filter \
'sed "s/-p //g" | xargs -r git show-branch --independent | sed "s/\</-p /g"'
This is inspired by the same thread on the kernel mailing list than Lucas’ solution. However it does not require Ruby and is a one-liner. It does require GNU versions of xargs and sed though.