I think DOM will be the best fit for your purpose, and you don't need to reinvent everything by yourself. There is at least one module available for DOM in Perl. Go CPAN check out XML::DOM. You can also do a search, see whether there are other modules.
As for data structure, as long as it is acceptable to the DOM module you choose, it is fine.
As far as I remember, neither XML::DOM nor XML::LibXML (or, to be exact, the respective "Document" subclasses) require
a DTD. But you can verify your document against a DTD after you're done building (e. g. XML::LibXML::Document has a method is_valid () which accepts an XML::LibXML::Dtd object).