I've been watching Leonard Susskind's particle physics lectures and in one lecture, he discusses a very simple gauge theory. We have a complex scalar field $\phi(x)$ with Lagrangian
$$\mathscr{L} = \partial_\mu \phi^* \partial^\mu \phi - V(\phi^* \phi)$$
and we want to do the gauge transformation $\phi(x) \to e^{i\theta(x)} \phi(x)$. But the derivative term in the Lagrangian is not invariant if $\theta$ varies from place to place, so we add a new vector field $A_\mu$, and define it to transform like $$A_\mu \to A_\mu + \partial_\mu \theta$$ under the gauge transformation. Then we change the Lagrangian to use covariant derivatives $D_\mu = \partial_\mu + iA_\mu$ instead of ordinary ones; now when the gauge transform is done all the derivatives of $\theta$ cancel out, and the result is invariant.
My question is: was there any freedom in choosing to add a vector field, with that specific gauge transformation law? Are there any other ways we could get gauge invariance here—by using a different transformation law, or with a different type of field (say, a scalar, tensor, or spinor) with some other transformation law?
More generally, how can we tell what type of field is needed and what its gauge transformation law should be, to get some particular Lagrangian to be invariant under some particular gauge transformation?