Is it possible to run out of nonce values? Miners can vary at least these things when searching for hashes:


A 32-bit nonce
Which transactions are included in the block.


Is it ever possible for a currency using the Bitcoin protocol to get 'stuck'? That is, can all combinations of parameters that miners are allowed to tweak not result in a hash that conforms to the difficulty?

One scenario using those parameters I listed could be an ASIC miner working on a brand new network. The difficulty should rise extremely quickly, but there would be very few transactions for him to work with.
Yes, it is possible to not find a valid block for all 2^32 possible nonces, and that is indeed the typical case. I believe only at the minimum difficulty level, sometimes still used as basis for finding shares in pooled mining, would you even average(!) one valid block out of all possible nonce values.

There is a timestamp field you can update, and there is an extra nonce that may not be so obvious because it goes into a hash calculation before being included, along nonce and timestamp, in the final double-SHA-256 hash.

Find more information here.