I would look into the Particle Electron and maybe the asset tracker(https://www.particle.io/products/hardware/asset-tracker)  it will have everything you need to get your project going.

The Arduino GSM shield is.. interesting. Pretty power hungry and doesn't work well unless you supply it with like 2A or something crazy like that(can't remember specifically). If you really want to use an arduino then yeah it could work. However, the particle has built in power regulation and is low power, and all those sweet things that ensure it will work right out of the box. Plug in the battery and follow the instructions. I set one up in like 30 minutes the other day after not knowing anything about it. I have a GSM plan, but I haven't used it for any projects yet. 

This could indeed be a simple solution, I ll look into the specs and see how customizable it is.

The power consumption of the GSM shields indeed is something that got me worried already. Thank you

By and large, GPS devices have a serial interface, so you'll need to hook the Rx/Tx from the Arduino to the GPS unit, or use the bit-banging serial simulator. The interface is usually 9600 baud standard ASCII, it's easy to find this on the net.

You *may* have to convert the TTL voltage levels from the micro to RS-232 levels, but that's straightforward. It depends on the board you get.

You can get GPS modules on eBay for about $15.

One problem: GPS from a cold start will take a long time to find all the satellites. The modern systems do this once on first powerup, then keep track of the time of day so that when you next boot them up they know which satellites should be visible in the sky.

This won't work if you, for example, fly the device across the country. When it wakes up it'll have the wrong idea of which satellites are visible, and will have to go through the cold boot process again.

Some GPS devices have battery backup and an embedded RTC for this reason.

How many do you need, and how sensitive do they have to be? I've got a couple of high-end units that work with battery backup and remote antenna (ie - a long wire going to a plastic "puck") that were taken from cell phone towers, and I could send you one or two if that would meet your needs.

I was thinking of an Arduino Mini. The thing about the GPS modules is that I'm not really sure how they compare in power consumption (let's say for 1 time full bootup + obtaining coordinates) and what kinds of interface protocols there are.

The full boot-up you mentioned might indeed be an issue. Do you think it's possible to work around this by having the arduino telling the GPS module what its last position etc? That again comes down to which interface a simple GPS module comes with I suppose.

For now I'll just start with 1 prototype and see where that gets me. I might need more for additional devices later on but I'll decide after some field testing. Sensitivity-wise I' m looking for a general localization like +- 20-30 yards, nothing fancy. I fear that high-end devices come at the cost of of size and power consumption which I both have to keep to a minimum. But thanks a lot for the kind offer.