Indeed, gauge invariance is not a physical property. It's the property of the description of observable facts, and it implies that only gauge-invariant quantities can represent observables. That precisely must be so, because (!) indeed "a change of gauge is just an artefact of how theorists represent the laws of physics mathematically." Nothing that depends on some arbitrary choice of a theorist can represent an observable.
Your last sentence is utterly errorneous: If you don't mention that you describe nature with a gauge theory you cannot even define, which empirically testable predictions you model indeed means.
Of course, you can formulate classical electrodynamics entirely without the potentials, dealing only with observable quantities, i.e., the em. field, ##(\vec{E},\vec{B})##, as well as the sources, ##(\rho,\vec{j})##. This is not possible for QED, because you need the potentials for a description in terms of a local QFT. Already for the free field, where you can use radiation gauge to fix the gauge entirely, the transverse vector potential cannot represent a local observable, because it does not fulfill the microcausality constraint, which is why you have to build the observables in terms of the field operators ##(\vec{E},\vec{B})##, which fulfill it. Particularly the correct Hamilton density is ##\mathcal{H}=(\vec{E}^2+\vec{B}^2)/2##.