Your question can be resolved through understanding some terms better.
A coin flip does not 'contain information.' A coin flip is a stochastic process that generates a random outcome. A well-defined stochastic process is associated with a probability distribution that has a well-defined associated information-entropy. For the toss of a fair-coin, this is one bit.
When you measure the result of a coin-toss, you gain information about the state of the coin. If your previous information was, "The coin's value is determined by a coin toss," and your new information is, "Heads," your information about the coin's state has increased by 1 bit. This will be exactly the same as measuring the difference in entropy for your prior and posterior distributions.
Now that we have that background, we can really talk about information in fundamental physics. While a coin-flip, as we have considered it is a stochastic process, it is also a deterministic process. That is, if we took an accounting of the exact dynamics of the flip and the exact initial state of the coin before the toss, we could calculate (supposing we had enough computational power) the final state of the coin perfectly and we will have gained no information about the coins state from measuring it.
In fundamental physics, it is possible to treat ANY physical process in this way, as the dynamical evolution of some closed system. Hence the principle that 'information is never destroyed'. This is just (sloppy?) shorthand for: Any state is recoverable as long as we perfectly understand the exact state and dynamics of some large enough system (where large enough system might be the entire universe) and have unlimited computational power.
Hopefully this is enough to understand why it's strange to say that measurement collapse 'creates information.' Information is a property of a description (in our case a probability distribution over state). When we measure something (quantum mechanically or no), we are increasing the accuracy of our description.
You might wonder if wave-function collapse destroys information. If you understand paragraph 4 you will see that it does not. The trick is that the information is stored in some larger system, one that includes the quantum object and you the measurement-taker. Some exterior being could in principle reverse this larger system and somehow recover the original state of the quantum system. There are a lot of problems with this- quantum states cannot be measured to unlimited accuracy or reversed as easily as classical states, and again you would need nearly unlimited computational resources.