I'm seeking a reference or a sketch for any sort of normal form that would enable rapid enumeration without redundancies of the elements of hyperbolic triangle groups and/or von Dyck groups.

This thesis contains a complete rewriting system for every triangle group (see Section C at the end of the thesis). Then normal forms are just words that do not contain left parts of the rewriting rules (which is just a finite set of words). This gives enumeration of all elements without redundancies. 


The general reference for this topic is "Word processing in groups", Epstein et. al., MR1161694 (93i:20036). Your groups all have automatic structures, and that book gives an enumeration method as you ask for, which applies to any automatic structure on a group. 

