BTW, how can you run out of nonce values? Can't you just continue incrementing the number, or are you talking about the fact that a integer (or whatever the data type is) has a numeric limit?
The nonce in the block header is a 4 byte integer. Therefore there are only 4294967296 possible nonce values for any given header. After that, you need to modify the header in some other way to gain another 4294967296 nonce attempts. Common ways to modify the header are to adjust the 4 byte timestamp or to change the transaction list so as to get a new merkle root.
I guess I'm curious as to how this tree is built.
There are no protocol rules on what software or function you must use to calculate the merkle root. I haven't looked closely enough at any of the existing miner software to know how they manage it. Each software developer is allowed to implement that in whatever way they see fit as long as the result is a properly generated merkle root.