Since we're just trying to produce a specific hash output, couldn't the nonce also include letters or otherwise random bits?
The nonce is an arbitrary string of bits with no particular meaning. Typically they are converted into an unsigned integer for convenience. Every possible set of nonce bits has a corresponding integer in this representation.
To get letter in a nonce, you'd have to present the bits in the nonce in some encoding scheme that had some way to encode letters. There is no such scheme in common use.
Technically, the nonce is just 4 bytes that are ignored. There's no reason why the block couldn't contain "Nick" in ASCII, or somebody's phone number.
That being said:
- the fastest way to mine is to start with a nonce of all 0's, then increment it.
- an easier way to embed data into the blockchain is to use fields in the coinbase.