Arduino on battery getting unstable if temperature falls
To answer your modified question:

Running the ATmega328p at 16Mhz with 3.7v is out of spec - see this EESE answer for reference or the ATmega datasheet - so the obvious solution would be to lower its speed to 8Mhz.

But since you also mentioned that there is an additional GSM breakout board involved (Adafruit Fona), which expects UART (in auto-baud mode) Rx/Tx connection, it might not be that trivial. Further exploration of the Fona library's source code reveals that it has several hard-coded delays (see Adafruit_FONA.cpp::begin, for example), but its core seems to be implemented inside the Adafruit_FONA::readline method, which uses an underlying Stream, which in turns comes from a Software/Hardware serial object, as shown in the FONAtest.ino example that comes with the library. 

From my experience, Software/Hardware serial should work fine on 8Mhz, except maybe when using high baud rates, which is solvable. 
The hard-coded delays doesn't look like they should cause actual damage except for delay, but you could cut them in half just to see if you can make the library work.

Additional aspect that you should consider is the comment from Adafruit's Fona product page, regarding pin Vio:


  This is the pin that you MUST drive with an external voltage from
  3V-5V to set the logic level converter


So, despite that from the datasheet, the Fona seems to have a voltage regulator, you might still want to consider adding a decoupling capacitor between Vcc and Gnd of your battery, to  mitigate transient current draws from any component in your circuit.