Rebasing with merges and conflict resolutions

I am trying to use rebase to straighten out a couple topic branches' histories
and running into nothing but troubles and I'm wondering if:
   a) I'm doing it wrong (highly likely)
   b) what I want is not possible
   c) banana!

Two contributors worked in tandem on a particular project, constantly merging back and forth between each other creating a history of 118 commits total with 37 of them being merge commits, 7 of those merge commits having conflict resolutions involved.

I would /like/ to rebase those into a more linear revision history, but I
can't seem to find any set of commands that doesn't have me:
   a) Manually re-doing every conflict resolution and merge (git rebase -p master)
   b) Drastically diverging from the original topic branch and entering some
      sort of mergeless hell (git rebase master)

Is it even possible to straighten this out without a massive rework of these commits?

In the future, is there a better way for two developers to work in the same back-and-forth fashion (code ping pong!) without leading to *heavily* merged histories that are unpossible to untangle?

Halp!

Cheers,
-R. Tyler Ballance
--------------------------------------
 Jabber: rtyler@jabber.org
 GitHub: http://github.com/rtyler
Twitter: http://twitter.com/agentdero
   Blog: http://unethicalblogger.com