A) There can be about 2^160 addresses. This is a very large number, and there's no concern that we'll start having collisions any time soon. In the very unlikely that we start generating addresses so fast that it's plausible a collision may happen before the end of the universe, we can increase the hash size and it'll be solved forever.
B) It's not technically impossible - it's just so extremely unlikely that it can be safely assumed that it will never happen, as above. This is not a "oh, you'll never win the lotto" kind of unlikely. It's a "You can generate addresses using all the computing power on the planet until humanity no longer exists as a species and you'll never see a collision" kind of unlikely.
C) The coins/bills have a keypair assigned. The BTC are sent to the public key which is printed on the outside so you can verify the balance. To redeem them you crack them open to discover the private key, which lets you import them into your wallet and/or spend the coins.
D) You can generate addresses all you want and no one will know or care. The blockchain only grows when an address actually receives coins. The transaction fees for small or frequent spends are there to prevent abuse. If you want to send tiny amounts to a billion addresses, that's fine - you'll have to pay a large transaction fee, and then we'll store it for you.