What is a gauge theory? Please note that I just read about 20 forum discussions, none of which answered my question. This question is related to my earlier question Is spacetime symmetry a gauge symmetry?.
I am looking for a definition of "Gauge Theory" in purely formal terms. What is a gauge theory in the context of classical field theory?
Suppose you are given a number of fields $\{\phi_i\},$    $i=1,\dots,n$ on $\mathbb{R^4}$, which are defined to transform in some way (and perhaps mix) under Poincaré Transformations, a Lagrangian density $\mathcal{L}$ (which depends on the values of the fields and their derivatives) and an action (integral of $\mathcal{L}$ evaluated at fields evaluated at points). Further suppose that for all fields $\phi=(\phi_i)$ and Poincaré transformations $P$ $$S[\phi]=S[P\cdot \phi].$$ I think most people will agree that this data specifies a Classical Special Relativistic field theory. Is it a meaningfull question to ask: "What are the gauge symmetries of this theory?" ? In other words: Is this a well-defined notion with only the data given above? Given some transformation $\phi\mapsto \phi'$, is it meaningfull to ask "Is this a gauge transformation?"?
There seems to be some controversy "whether GR is a gauge theory" and "in what sense GR is a gauge theory", so I assume the answer to above question is no, but I wanted to be sure. I am aware of an article by Terence Tao also called What is a gauge? where in his opinion a choice of coordinates is a special case of gauge fixing. 
To get back to the above question and make it more interesting than asking for "No" as an answer, consider the following:
As far as I know, free klein Gordon theory of a real scalar field in $3+1$ dimensions has no gauge symmetries (whatever that means). How would you construct a classical field theory that is "physically equivalent" to klein Gordon theory after removing gauge degrees of freedom? I'm asking for an example if this is reasonably simple. 
Another version of the very first question is the following: Can one have the same Lagrangian with two different gauge groups making two different theories? Supposedly the fact that the canonical momentum associated to $A^0$ in Maxwell theory is non-dynamical (but rather constrained) somehow implies a gauge symmetry being present. However, if one cannot determine the gauge transformations by any well-defined procedure, could one construct a self-consistent (perhaps physically meaningless) theory, where all components of $A$ are considered to be "observable"? I assume not, since the time evolution of such field configurations would turn out to not be unique. 
On the other hand, in the theory of a complex scalar field, all momenta are dynamical and the equation of motion fixes the entire field for all time given reasonable initial conditions. Is it possible in this case to consider something else as "the gauge symmetry" of the theory, perhaps nothing, rather than $U(1)$?
 A: *

*A gauge symmetry is simply a symmetry transformation of the action that depends non-trivially on spacetime. You can ask for all physical theories whether such transformations exist. For the case of particle mechanics of finitely many degrees of freedom (where the gauge symmetry then only depends on time), it is known that the existence of a gauge symmetry is equivalent to a constraint in the Hamiltonian formulation. Such constraints arise from the Legendre transformation of the Lagrangian being non-invertible, therefore the condition
$$ \det\left(\frac{\partial L(q,\dot{q})}{\partial\dot{q}\partial\dot{q}}\right) = 0,$$
with $L$ the Lagrangian and $q,\dot{q}$ the generalized coordinates detects the presence of gauge symmetries. A very good reference for the constrained Hamiltonian view of gauge theories and their quantization by the BRST procedure is Henneaux' and Teitelboim's book "Quantization of gauge systems".

*When a physicist speaks of a "gauge theory", they usually do not mean the very generic case of a "theory with gauge symmetry" from point 1 (but sometimes they do mean this - pay attention to the context!). They often mean a theory with a gauge field, such as Yang-Mills theory (see also this answer of mine) or Chern-Simons theory. The "controversy" over whether "GR is a gauge theory" stems from the fact that the "gauge field" of GR are the Christoffel symbols, which are considered non-dynamical fields derived from the metric unless you are using the Palatini formalism. Maxwellian electrodynamics is the archetypical example of a Yang-Mills gauge theory with gauge group $\mathrm{U}(1)$.

*It is a rather deep result of quantum field theory that every massless vector field is a gauge field, for a very brief overview over the reasoning, see the latter part of this answer of mine. The constraint $\pi^0 \approx 0$ for the canonical momentum associated to $A^0$ is not a feature of the gauge theory, it's simply a feature of all vector fields - even a massive vector field "suffers" from this constraint. This constraint of course formally also generates some gauge symmetry in the sense of point 1, but this symmetry is easily eliminated by gauge fixing. The constraint that makes electromagnetism a "gauge theory" is the secondary constraint incurred from the consistency condition $\dot{\pi}^0 \approx 0$, which yields $\partial_i \pi^i \approx 0$, which is Gauß' law!1 Together with the gauge fixing for the first transformation, the half-fixed theory of a massless vector field then has the familiar residual gauge symmetry $A^i \mapsto A^i + \partial^i \epsilon$ for any function $\epsilon$. Once again, if you wish to study this in formal detail, I recommend Henneaux/Teitelboim's book, in which  the example of Maxwellian theory is chapter 19.

*It is "easy" to artificially introduce additional degrees of freedom into a Hamiltonian that are redundant, leading to the Hamiltonian theory becoming constrained and therefore the action developing gauge symmetries, see this answer of mine. It is also "easy" to introduce gauge fields into a Lagrangian simply by declaring all fields to be uncharged under whatever gauge group you wish and adding the corresponding Yang-Mills term to the action. Of course, this is completely useless, since these fields interact with nothing and you can just omit them.

1Note that this breaks a perceived symmetry between the electric and magnetic field equations - in the action formalism with the vector potential as the dynamical variable, Gauß' law is not an equation of motion, it is fulfilled prior to solving the equations of motion! See also this answer of mine.
