Did you look at this use.perl.org post: Simplified parseable Changes: draft 2, that would give you a starting format for a change file.

BTW, I am not sure I really like the format, and I am pretty sure I won't convert old change files to it, but if this format ends up being widely used, then I will gladly adopt it for future modules.