I've looked in to little tumble generators (I don't know the actual term, something that could generate power off of movement) but again, my knowledge is lacking in that department.
Would make for neat little animal tracking devices, if they could generate power from movement, store in a battery, and then 'pulse' out on a regular interval (whatever interval is allowed by the generation from the shake/tumble generator).
A lot depends on how often you actually need to gather GPS data, and how often you need to report it. A GPS can use a relatively large amount of power while first getting a fix, but then updating that fix later, if it hasn't moved too far, will use a lot less power.
The datasheet for a GPS module should tell you the power consumption during various operations, and how long those operations can take, so you can figure out the power needs for a given updating schedule.
You could probably do some clever things, like include an acceleration sensor and only update the GPS when you infer from the acceleration sensor that you've moved.
Similar considerations apply to reporting data. Frequent reporting will use more power than saving up the data and sending it one bigger batch, because there is overhead in setting up a connection to whatever you are reporting to.
There are commercially available GPS trackers that run for two weeks on two AA alkaline batteries or three weeks on AA lithium batteries. I don't think the ones I saw reported wirelessly...they were the kind you have to retrieve to get the tracking log, but this suggests that an AA GPS tracker with wireless reporting with enough runtime to be quite useful is feasible for a lot of applications.