Can someone give me a rigorous definition of the degrees of freedom and explain how this definition addresses the questions above?
Yes. A good, modern, and rigorous definition has been available for at least one hundred years. See, for example, the textbook by Whittaker titled "A Treatise on the Analytical Dynamics of Particles and Rigid Bodies," which was written in 1917. (As an interesting aside, Dirac used this textbook for his studies of classical mechanics and their relation to quantum mechanics, in particular the definition of Poisson brackets and their relation to communtators in quantum mechanics.)
The textbook is no longer subject to copyright and is available online for free. (Google the title plus the term "pdf" to find it).
In particular, section 25 regarding "Holonomic and non-Holonomic systems" provides a definition via the following few paragraphs:
If we consider the motion of a sphere of given radius, which is constrained
to move in contact with a given fixed plane, which we can take as the plane
of xy, the configuration of the sphere at any instant is completely specified
by five coordinates, namely the two rectangular coordinates (x, y) of the
center of the sphere and the three Eulerian angles $\theta$, $\phi$, and $\psi$, which specify the orientation of the sphere about its center. The sphere can take
up any position whatever, so long as it is in contact with the plane; the five coordinates (x, y, $\theta$, $\phi$, $\psi$) can therefore have any arbitrary values.
Note that in the above-quoted paragraph, "any position whatsoever" means that the sphere can slip, slide, spin in place, roll, and do any type of motion so long as a point stays in contact with the plane. This is Whittaker's case of a "perfectly smooth" plane discussed below. He contrasts this in his paragraph below with a "perfectly rough" plane where the sphere has to roll and can't slip along.
If now the plane is smooth, the displacement from any position, defined
by the coordinates (x, y, $\theta$, $\phi$, $\psi$), to any adjacent position, defined by the coordinates (x + $\delta$x, y + $\delta$y, $\theta + \delta\theta$, $\phi + \delta\phi$, $\psi + \delta \psi$), where $\delta$x, $\delta$y, $\delta\theta$, $\delta\phi$, $\delta\psi$ are arbitrary independent infinitesimal quantities, is a possible displacement, i.e. the sphere can perform it without violating the constraints of the system. But if the plane is perfectly rough, this is no longer the case when$\delta$x, $\delta$y, $\delta\theta$, $\delta\phi$, $\delta\psi$ are arbitrary; for now the condition that the displacement of the
point of contact is zero (to the first order of small quantities) must be
satisfied, and this implies that the quantities $\delta$x, $\delta$y, $\delta\theta$, $\delta\phi$, $\delta\psi$ are arbitrary are no
longer independent, but are mutually connected (in fact, they must be such as to satisfy two non-integrable linear equations); so that in the case of the sphere on the perfectly rough plane, a displacement represented by arbitrary infinitesimal changes in the coordinates is not necessarily a possible displacement.
(Emphasis in original text.)
A dynamical system for which a displacement represented by arbitrary
infinitesimal changes in the coordinates is in general a possible displacement (as in the case of the sphere on the smooth plane) is said to be holonomic; when this condition is not satisfied (as in the case of the sphere on the rough plane) the system is said to be non-holonomic.
If ($\delta q_1$, $\delta q_2$, ..., $\delta q_n$) are arbitrary infinitesimal increments of the coordinates in a dynamical system, these will define a possible displacement if the system is holonomic, while for non-holonomic systems a certain number, say m, of equations must be satisfied between them in order that they may correspond to a possible displacement. The number (n — m) is called the number of degrees of freedom of the system. Holonomic systems are therefore characterized
by the fact that the number of degrees of freedom is equal to the number of independent coordinates required to specify the configuration of the system.
In the last quoted paragraph above, I have added a bold emphasis to the sentence defining the term "number of degrees of freedom."