Can you explain the complication you're thinking about? And what additional information you'd store?
If you think this problem can be solved by declaring today's version of tzdata immutable and final, then I'm afraid you're not being realistic. Timezones, DST rules, country borders will change and always have.
It doesn't have to be immutable and final, it can simply be versioned then :) cf what I said in my other reply, if you create a new timezone every time you change it, it seems you don't have that problem.