Huh, and I thought my family had monopoly on the "bloated Coca-Cola cans" technology!
Anyway, experimental facts: I've often seen cans expand in the freezer when forgotten for 24 hrs or so, and do testify to the mess they cause when exploding ;D. Don't try it unless you plan to wash your freezer thoroughly afterwards! Or carefully bag the can beforehand. On the other hand, never had a chance to observe expansion during slow thawing, although I know that if only partially frozen, a can's contents may restore to original "fizzy" state.
So, given that cans do expand if left long enough at below freezing temperatures, I think expansion while freezing has to do with:
1) Mainly the expansion of ice: put an unopened water bottle in the same conditions and you may end up with a cracked plastic bottle. Ice expands about 9% by volume compared to the original volume of water. Thinking of it, I'll have to measure the volume increase next time!
2) The release of $CO_2$ from ice: if you check the Coca-Cola ice before it melts, you can see that it is very porous, as opposed to the solid block obtained in the same conditions with a water bottle. Not saying that $CO_2$ expands, because it doesn't at these temperatures, but its separation from the liquid and the porous structure it creates may give some additional contribution to the expansion.
Assuming the above are reasonable hypotheses, we still have two open questions regarding your own observations:
• Why did you not observe expansion in the freezer more often? Likely, the cans were "frozen enough" not to slosh around when checked, but were not really frozen through and through. Complete freezing and release of $CO_2$ takes time, and it's possible you removed the cans from the freezer before significant expansion occurred. Or maybe the temperature was not low enough. Remember you have a syrup solution, not just water!
• Even so, why did the cans expand after taken out of the freezer? Preliminary observation: when you bring an already expanded, frozen can at room temperature, the gas definitely breaks the seal and escapes before anything else happens. If you really want to check it out, make sure to put the can in a roomy bowl first, or bag it! Makes a messy show again. In view of this, for a can that did not expand significantly yet in the freezer, I surmise that expansion at room temperature has to do entirely with expanding $CO_2$: First, when taken out of the freezer the can contains mostly ice and separated $CO_2$. The gas expands as it warms up, before the ice can melt, and bloats the can, but not sufficiently to break the seal. Second, as the ice melts and the liquid warms up towards room temperature, the $CO_2$ begins to dissolve back into the liquid since the can contents are still under pressure. After this point you won't see any gas escaping or liquid bubbling around the seal, just a bloated can.
There is plenty of room for experimentation here. Would be fun to check each point, but then it would waste a lot of Coca-Cola. Have fun! Hope this helps a little.