How is the balance checked by miners when new addresses are generated? How is it even possible to check all the transactions for balance when there are constantly new addresses being generated?
Bitcoin itself only needs to track the current set of spendable bitcoins.  It doesn't need to track bitcoins that have already been spent nor any information about who may receive bitcoins in the future (e.g. a new address).  

When you create a new address, you don't have to register it anywhere (indeed, you can create the address completely offline), so there is no global tracking of new addresses.  By default, only your wallet tracks information related to a new address.  When someone spends money to that address, then Bitcoin full verification nodes begin to store the address, as it now controls spendable bitcoins.  When you spend those bitcoins, full nodes stop storing the address.  If you later receive more bitcoins to the same address, full nodes will start storing it again.

Some websites continue to store information about historic transactions so they can show every transaction that affected an address.  This is an interesting feature, but it's not directly related to what full nodes do.  Full nodes only store the information related to the current set of spendable bitcoins (plus some additional unindexed information necessary in case they need to recover from a problem).