How did iPhone 4 know to switch timezone in Airplane Mode?
Since your phone is a Verizon iPhone, it got the time from the cell towers. (Verizon, along with Sprint and unlike AT&amp;T and T-Mobile, uses CDMA which broadcasts the local time from the cell towers.)

It must be that Airplane Mode is actually "don't transmit" mode instead of "don't transmit or receive" mode as I'd always assumed.

Edit my reasoning:


I know that CDMA phones get the local time from the cell towers (if you're driving, you can watch your phone switch time zones as you cross the border). 
I also know that cell towers broadcast their availability so they can be found by phones. It makes sense, then, that the time signal might be in this broadcast signal. 
One of the reasons Airplane Mode exists is to prevent transmissions from potentially disrupting aircraft systems. 
Turning off transmit functionality does not necessarily preclude receiving data. Leaving receive on may actually be a benefit, as the phone can passively monitor cell towers in the area so as to know which one it wants to talk to when/if Airplane Mode is turned off.
If you're passively listening to the towers already and they're broadcasting the time anyway, it would be logical to update the system time to whatever local time is since you already have the data available and you can give the user the most accurate information possible.