Confluently Persistent String Data Structure
What you seem to be looking for is not a data structure for strings themselves, but a grammar for representing concurrent actions on strings. The field of study for this is Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation