Q:

Checking if a receiver has enough coins

How do miners verify the blockchain transaction history to check if the sender has enough money if the address can be changed at any time?

A:

Bitcoin does not have the concept of account balance. Anyone who can provide a valid signature to the locking script of a particular transaction output can spend those bitcoins. As a result when you spend your bitcoins in a transaction, you have to include the transaction id and the output no. from which you earned those bitcoins. The nodes maintain a set of unspent transaction outputs (UTXOs) in the memory to check that this transaction output that has been referenced in the input has not been spent previously (this prevents double spending.)
If you want to send X BTC to a particular address, you will need to reference enough transactions in the input so that sum of all those unspent bitcoins >= X. This referenced transactions can come from different addresses. You just need to provide valid signature with your private key to show that you are the owner of those bitcoins. 

