I would think that using a pure Perl YAML encoder together with Tie::IxHash should keep the order of the keys. See AM's reply below, that doesn't seem to work :-(

If your data structure is reasonably fixed, you might even get through by using a text template and filling in the values. Usually that means having a machine-readable data schema to generate the template first.