Nonce size - Will it always be big enough? If I understand correctly, the block only has 4 bytes (32 bits) for the nonce.
Is it possible for the difficulty to become high enough that there are no nonce solutions?
If so, then what options does a miner have?
The difficulty is already to the point where it requires over a quadrillion hashes to solve a block. 2^32 is only 4 billion. Fewer than one in a billion times will there be any nonce that makes the block valid.

A miner simply has to try every possible nonce on a different block. He can vary the coinbase, the transaction set, and/or the block timestamp. Any change to any of these things results in a new chance for there to exist a valid nonce.

Often the best choice is to bump the timestamp, a practice called NTime rolling.

The block timestamp doesn't have to be exact anyway, so you can back the timestamp back, say, ten seconds before you start mining and then bump it up 20 times before giving up and getting a new block. At worst, your block timestamp will be off by a dozen seconds or so -- nobody cares about that.

After that, you probably want to get a new block because there might be some new transactions to include -- this not only improves the efficiency of the network as a whole but reduces the chances you'll miss out on a transaction fee.