1. One has no way of predicting what a hash function will spit out, that's why you add nonce to transactions and voila you are the winner if you get a hash below certain number.
Now the question is: Is it possible for every nonce coupled with transactions to produce a number greater then required? What happens then?
The nonce isn't the only thing that can be varied (e.g. extraNonce), so the practical answer is probably "not possible", but I'm not aware of any theoretical proof.
2. It's often cited that if you don't include transaction fee the miners won't include the transaction for a long time and if you do include the fee it will get 1 confirmation every 10 minutes. How do miners "know" that transaction fee is included if they work on hashes of transactions?
Solominers and pools can see the transactions and select the ones they wish to include. They are completely free to chose which and how many to include.
3. How does pool mining work?
I understand that each individual miner is handed a piece of the puzzle to solve.
That's not an accurate way to look at it. There is no "part of the puzzle". Only "the puzzle". The name of the game is to get a hash that starts with a some number of zeros (higher difficulty -> more zeros). In a pool, each participant sends in answers to the puzzle that are of some much easier difficulty. This allows the pool to gauge how much work they are doing and give out rewards in accordance with that.