Hola,
Posiblemente no hay entendido bien la pregunta, pero ...
Cita:
Iniciado por Antroz 
Con DOM, puedo agregar y eliminar elementos sin problema. Pero con SAX, no me cuadra como hacerlo.
Será porque SAX no está diseñado con ese objetivo. No dudo que sea posible usar SAX para actualizar un documento XML actualmente, pero originalmente no era ese su objetivo, para eso existen otras librerías.
Cita:
Iniciado por Antroz En el parser luego de la lectura tengo un ArrayList con todos los elementos y atributos.
¿Extraes un ArrayList con SAX? ¿Capturas todos los eventos para agregarlos a un árbol? ¿No sería mas adecuado usar una librería DOM directamente?
Saludos,