How often does the data change? I have a somewhat similar problem with my module Number::Phone::UK. That relies on a data set that changes occasionally, and while it has only changed locations on me once, the format of the files changes more often.

I decided not to make users download and parse the data themselves. Instead, I do that every so often and distribute it myself. It's a lot less work for me, the process is easier to test, and it's more reliable for my users.

As for the format in which I distribute the data - none of the standard tools for packaging perl modules handle non-perl files at all well. Consequently, the data is buried in another module Number::Phone::UK::Data, as a DBM::Deep database in a __DATA__ segment.