1 What other fields can we change in the message when mining, other than the nonce?
The timestamp, the coinbase transaction, the list of transacations included in the block.
2 Where is the extraNonce located?
My recollection is that the 'extraNonce' is the coinbase. See here where its put into the input of the coinbase transaction:
pblock->vtx[0].vin[0].scriptSig = CScript() << pblock->nBits << CBigNum(nExtraNonce);
pblock->hashMerkleRoot = pblock->BuildMerkleTree();
3 Where is the time (and can we change it as we see fit while mining, or are we required to keep it in a certain range)?
The time is in the header, but it must be kept in a sensible range.
Good answers. I was just gonna say work with 6 other dwarfs and capitalize on woman work.