Does 4 byte Nonce enough to proof of work? Is it always possible to find an hash value of a block, smaller than the current difficulty, just using 4 byte (Nonce) ? How can we be sure about it ?
No, it is not enough.

There is extra-nonce field. The scriptSig of coinbase transaction.