well, i haven't worked with Data::Dumper, but it looks promising...
i was thinking you should look at XML... there are modules to do most of the work, it is very standard(or rather is a standard), it will handle arbitrary data sets quite well, and it will handle changing the structure as well.