I would like to really understand what the mathematical as well as Physical meaning of coordinate invariance is. I have pretended to know what this means, but upon thinking a little harder today, I am now convinced I don't know what it means. In any case, as far as I know calculations still are always done in some coordinates, in some space.
Coordinate invariance in physics simply means that laws of physics are and should be independent of the coordinate system used. It does not imply coordinate free. This is because the laws of physics are written in the form of tensorial equations, and tensors are independent of the coordinate system used.
Perhaps you could explain what exactly led you to question your understanding... The physical meaning of coordinate invariance is pretty simple. It's just that the laws of physics cannot depend upon your choice of coordinates as long as the reference frame you're working in is inertial. So if you were to perform a coordinate transformation from one inertial frame to another, the mathematical form of your equations of motion will not change and are said to be coordinate invariant.