How to allow batch editing "m to n" relationships (tags on elements)

I have the same "problem" as WordPress, as in I need to allow batch changes of tags. The relationship is m to n; each element can have multiple tags. Now my main problem is that the elements might already have individual tags assigned, so selecting multiple elements for editing might result in having many "partially" matching tags.

The requirement would be that:

  1. tag(s) can be applied to a single element
  2. tag(s) can be removed from a single element
  3. not yet or partially assigned tag(s) can be added to selected elements
  4. assigned or partially assigned tag(s) can be removed from selected elements

What I struggle with is:

  1. How can we allow the user to keep control of the changes in progress (which tag is being remove, which is being added and this per element?)
  2. How to allow removing and assigning tags in one single go, as tags might be missing on some of the selected element, already be present on others?

Some input would be greatly appreciated! And I know that WordPress seems to not have solved this, so this must be a tough question. But I still have hope...