Starting from the beginning, the universe started with an explosion which generated, as the initial plasma cooled, mainly hydrogen and helium (The creation of hydrogen and helium).
The heavier elements such as carbon and oxygen were created later, as the first generation of stars collapsed and exploded in supernovae. It is thought that our Sun is a 3rd generation star (see "What is meant by the theory that the sun is a third generation star?"). Hence, we can say that the presence of carbon and oxygen in the solar system is caused by the stellar explosions which came before the formation of our Sun.
When the planets formed around the Sun, carbon and oxygen were part of the mix of elements that came together.
The processes leading to the formation of the early atmosphere, before life started on Earth are unclear, though it is certain that there were frequent meteor impacts and volcanic eruptions in this period (because the solar system was much more crowded and the Earth's core was much hotter -- see for example IFL Science).
If we look at nearby planets, we see that Mars has an atmosphere of 95% carbon dioxide, and Venus has 96%. On Earth it makes up only 0.04% of our atmosphere (Atmosphere of the Earth). The difference is due to life on Earth, which has taken CO2 out of the atmosphere.
Coal deposits were laid down in the Carboniferous, as stated in the question. At the time, atmospheric CO2 was at much higher concentrations, so the growth may have been denser, which could (I don't have a reference for this) have contributed to the fact that material got buried before it could rot (see "The Age of Oxygen" for some discussion).