The system has three degrees of freedom, but that doesn't mean that any three numbers necessarily specify the full state of the system. If you have $x_1$, $y_1$, and $y_2$, then as you have noticed there are two possible solutions to $x_2$. But you can fully specify the system with $x_1$, $y_1$ and an angle specifying which direction the second particle is in relative to the first.
Can you count time as a parameter?
No. The configuration is what potentially changes over time. So the equations of motion are a function from time, into the set of configurations. Time is the domain and the set of configurations is the codomain and the equations of motion is the function from the domain to the codomain.
Can't you always increase the number of parameters (even if it has no effect) and still determine the configuration of the system?
They would not be independent.
In the case of a pendulum, most texts say it has only one degree of freedom,
That's the planar pendulum, confined to rotate in a plane, like a grandfather clock.
In the case of projectile motion, the projectile has 3 degrees of freedom, right?
Yes. At each point in time you have to specify three coordinates to specify the configuration at that time. More if it is extended and can have orientation, even more if it is not rigid.
Keep in mind that a degree of freedom is about the space of possible configurations. It isn't about any one particular equation of motion.
Can someone give me a rigorous definition of the degrees of freedom and explain how this definition addresses the questions above?
The only place it seems you stumbled is about independence. You should be able to freely adjust any of the coordinates in the degree of freedom within some little bit and have a different configuration.
But this is also a false generality. For $N$ particles the degrees of freedom is $3N$ and sometimes you can pretend there are fewer by pretending that some constraint is exact when it is not actually exact. For instance a real pendulum can and does elongate a little bit and the place it pivots can wiggle a little bit and so forth. The one degree of freedom is really about ignoring the other degrees of freedom.
So just have $3N$ and then start eliminating ones you don't care about whose dynamics hardly change in an important way. And just don't over eliminate, you should retain enough to describe your system. In the case of the pendulum when you know the end point and you assume the rigidity and one part fixed, then you know the whole thing.
What can you really gain by pretending to have more generality than is really there?
Best Answer
I think that the term "degree of freedom" had been initially derived from the observation that the system may be completely described by $n$ independent coordinates - they said: "well, if this $n$ is really a characteristic of the system - let's give it a name!". It is my personal belief that the name comes from a classical kinematics: if a body can't move "freely" in some direction - this reduces $n$ by one.
Therefore, your question may be reduced to the following one: "why the number of independent coordinates which describe the system completely does not depend on coordinates themselves?". Am I right here?
Mathematical answer:
We describe systems by means of linear algebra. There is a concept of a basis in linear algebra: a (minimal) set of independent vectors is a basis, while the projection of any vector from a state-space of a system on this set preserves the norm of the state-space vectors (there are many alternative definitions).
What the above definition says is that if you find a set of (independent) vectors, and can represent any state of the system in terms of these vectors without loosing any information - this set of vectors is a basis.
Why do we require the set of vectors to be minimal? Well, you can add another independent vector to this set, but if the system has no component in this additional coordinate - this vector is redundant. Real life example: you can describe the position of a body using three vector coordinates (x, y, z). You can expand this set of three vectors with a vector of velocity of the wind (which is clearly independent with any of the positional vectors of the body), but we need not worry what the wind is. We are measuring the position of a body.
So, we have a basis, what now? Well, there is a theorem in linear algebra which proves that if you have a basis for the state-space, and you find another basis, then the dimensions of these bases are the same. This means that you always need exactly $n$ independent coordinates to describe the system completely (without loss of information).
Intuitive answer:
This one is very tricky, because all the discussion about "coordinates" and "independence" is bound to the framework of linear algebra. Really, I find it very hard to reason the above statements intuitively.
Maybe this: assume that there is finite number of properties of interest in the system (as it is usually the case). You are given $n$ boundary conditions which are not related - none of them can be derived from the rest. In this case, each boundary condition allows you to express a single property of your system. If you find that these $n$ boundary conditions describe all the properties of interest - this means that you have $n$ properties of interest.
Now, if you're given with $m > n$ unrelated boundary conditions, you can express $m$ properties of your system. However, we have already shown that you have just $n$ properties of interest. Conclusion: the $m$ unrelated boundary conditions describe $m - n$ parameters which you are not interested in. Throw them away because they obscure your view.