I believe this is currently done, i.e. timezone databases track not only the current timezone information but store the valid dates for which a set of timezone rules apply.

This would be necessary not only for the example provided in the link, but also for larger changes, like several years ago when the US extended DST hours, and several other countries followed suit. (i.e. DST now begins on the second Sunday of March, rather than later in April)