Regarding independence of generalized co-ordinates In the general scheme of classical mechanics, for a given set of variables, say $\{q_i,p_i\}$, we always impose the conditions, that these variables are independent, that is,
$$\frac{\partial q_i}{
\partial q_j}=\delta_{ij}.$$
Now, is it really justified in general? Since, they always have some implicit dependency depending on the problem, and moreover, this holds for conjugate momenta too.
 A: Perhaps a helpful comment is that when given a system of $N$ point particles with $3N-n$ holonomic constraints, and when we say that the generalized coordinates and their generalized velocities $(q^1,\ldots,q^n,v^1,\dots,v^n)$ are $2n$ independent variables, we mean before imposing the EOM, i.e. Lagrange equations, which are $n$ 2nd-order ODEs. After solving the ODEs they are no longer independent. See also this related Phys.SE post.
A: Given a set of coordinates $\mathbf x$, the partial derivative of a function with respect to the coordinate $x_i$ is defined by varying $x_i$ while holding the other coordinates fixed.  Explicitly,
$$\frac{\partial f}{\partial x_i} = \lim_{\epsilon\rightarrow 0}\frac{f(x_1,\ldots,\color{red}{x_i+\epsilon},\ldots) - f(x_1,\ldots,\color{red}{x_i},\ldots)}{\epsilon}$$
If we have that $f(\mathbf x) = x_j$, then this straightforwardly implies that $\partial f/\partial x_i = \delta_{ij}$.

Since, they always have some implicit dependency depending on the problem, and moreover, this holds for conjugate momenta too.

The generalized coordinates and momenta never have implicit dependency on one another. Part of the definition of a good set of coordinates is that in a neighborhood of any point in the space, we may vary any one coordinate while holding the others fixed. If a coordinate is fixed by the values of the others, then the coordinate system itself is ill-defined (at least from the standpoint of Lagrangian or Hamiltonian dynamics, in which the generalized coordinates and momenta are coordinates on a manifold).
