Can't we change the block data instead of a nonce? In the process of solving a hash puzzle, isn't it possible to change the transaction data instead of changing a nonce?
It's possible, and this does happen (refered to as extraNonce), but this is orders of magnitude more resource intensive to do, as you need at least the left hand side of the merkle tree, rather than just 64 bytes of the header. 

In Bitcoin the nonce is only 32 bits, which means every 4.2 Billion hashes you need to either update the timestamp, or modify the transaction tree to create fresh work. For a standard block today, this is more than 22 SHA256 hash invocations, versus less than one for modifying the nonce alone.