I have done some of this before
Lithium ion and lithium polymer batteries are useless at low temperatures. There was a lot of laughter here when commentards found out that a mini-sub was powered by a crate full of D batteries. That only had to work down to 0 centigrade. I have not seen batteries quoted for really low temperatures, so you might be looking for some sort of thermos flask for the batteries.
Looks like you spotted the problem with GSM: at altitude, many cells will be within range. The network operators will not be happy if you broadcast to a dozen cells at once. I have not done APRS, but I suspect it has some of the same challenges for the power supply as GSM. The average power may be reasonable, but the radio needs to take sharp bursts of power. This means you will need short leads and good contacts between the radio and the battery. Some kind person replaced my gold plated folded sheet metal contacts with helical steel springs (inductors with a huge contact resistance). That was sufficient to prevent the GSM module getting the sudden bursts of power it needed.
For release, I would go test the following in a freezer: Connect the balloon to the decent module with fuse wire and break it with a large current. Go nuts on the current because the fuse wire will get covered in ice. Use multiple methods for deciding when to release: GPS reports target altitude, GPS reports minimum acceptable altitude and consistently descending, time limit and remote control from your radio (you never know - it might still be working).
Read the instructions for your GPS. Many of them are optimised on the assumption that you must be on the surface of the earth, and that you want the signals that have been reflected off buildings (Reflected signals cause multipath error, but that may be preferable on the ground when the direct signals are blocked). There are often manufacturer specific 'NMEA' commands that will reconfigure a GPS for use at altitude.
Passive antennas will work at very low temperatures - if your GPS can use a passive antenna. If you have to use an active antenna, check the specs to find out if it will work at low temperatures. Read the real instructions for the antenna. The salesman will tell you what he thinks you want to hear. There are good signals at altitude, and plenty of satellites will be in view, but the kit will be working below the tested temperature range while covered in ice. Many GPS antennas assume they are stuck to the top of a car, and need a ground plane (sheet of metal about 30cm in diameter) to work according to spec (this include plenty of antennas for hand-held GPS devices). Use a coating that repels water: you can get them in spray cans (Often very poisonous. Read the instructions carefully and do not use indoors). Spray all the electronics as well (except the connectors).
It is safe to assume your GPS and your radio will not work at the same time. If you cut the weight by removing the RF shielding from you GPS, radio or CPU then none of them will work at the same time. Make sure you can send the last __valid__ GPS fix. If the parts work individually, but not when packed together, add small capacitors connecting each connection between modules to ground. If you cannot keep the GPS and radio antennas apart, point the radio antenna's weakest transmission direction at the GPS antennas worst reception direction. The frequencies are very different, but putting a powerful radio transmitter right next to a very sensitive receiver is always asking for trouble. GPS likes short antenna cables - especially if you use a passive antenna. The really thin light weight cable is poorly shielded and will pick up too much signal from everything that can confuse the GPS.