dom4j or jdom are probably the most elegant, you can write code how you like it. Dom4j has builders if I recall, and yes the code is more verbose.
Element.addElement("x").setAttribute("x", "y").xxxxx;
Take a look at XOM. It's fast, simple, correct, and isn't verbose.
Why don't you just use JAXB anyway.. then the problem becomes a very simple object to object mapping and you avoid xml altogether.