How can someone mine bitcoins at billions or trillions of hashes per second when the nonce is only 2^32 in size?
The timestamp in blocks does not need to be set to the actual time of the current hash. So during mining, the timestamp can be moved when the nonce is exhausted even if the actual time is not that timestamp.

There are also other ways to change block headers that do not require changing the timestamp. Miners frequently add a value to the coinbase part of their coinbase transaction which is referred to as an extranonce. Miners will increment that in order to change the merkle root every time they exhaust one set of nonces so as to allow for even more nonce possibilities. Furthermore, other things can be done such as permuting transaction order, selecting new transactions, changing coinbase output scripts, etc. All of these ways of changing the block hash allows for miners to do trillions of hashes per second.