The number of independent variables in the Lagrangian and Hamiltonian methods in Classical Mechanics It's told in Landau - Classical Mechanics, that in the Hamiltonian method, generalized coordinates $q_j$ and generalized momenta $p_j$ are independent variables of a mechanical system. Anyway, in the case of Lagrangian method only generalized coordinates $q_j$ are independent. In this case generalized velocities are not independent, as they are the derivatives of coordinates.
So, as I understood, in the first method, there are twice more independent variables, than in the second. This fact is used during the variation of action and finding the equations of motion.
My question is, can the number of independent variables of the same system be different in these cases? Besides that, how can the momenta be independent from coordinates, if we have this equation $$p=\frac{\partial L}{\partial \dot{q}}.$$
 A: $q_j$ and $\dot q_j$ are independent. I think it's more straightforward (at first) to think of this in terms of Newton's equations of motion, where the force determines the accelerations of the various particles, than in terms of the more abstract Hamiltonian methods. Because the forces determine the accelerations, not the velocities, both the initial positions and the initial velocities have to be given to determine the trajectories, which is just to say that the $q_j$ and the $\dot q_j$ independently determine the trajectories.
Note that the Lagrangian function is written as a function of both $q_j$ and $\dot q_j$, $L(q_j,\dot q_j)$, which makes sense of the equation for the momenta that you cite, $p_j=\frac{\partial L(q_j,\dot q_j)}{\partial \dot q_j}$.
So, there are the same numbers of independent variables in the Lagrangian and in the Hamiltonian formalisms.
A: 1L) The (generalized) position $q$ and (generalized) velocity $v$ are independent variables of the Lagrangian $L(q,v,t)$, cf. e.g. this Phys.SE post.
1H) The position $q$ and momentum $p$ are independent variables of the Hamiltonian $H(q,p,t)$.
2L) The position path $q:[t_i,t_f] \to \mathbb{R}$ and velocity path $\dot{q}:[t_i,t_f] \to \mathbb{R}$ are not independent in the Lagrangian action $$S_L[q]~=~ \int_{t_i}^{t_f}\!dt \ L(q ,\dot{q},t).$$
See also this Phys.SE post.
2H) The position path $q:[t_i,t_f] \to \mathbb{R}$ and momentum path $p:[t_i,t_f] \to \mathbb{R}$ are independent in the Hamiltonian action
$$S_H[q,p]~=~\int_{t_i}^{t_f}\! dt~(p \dot{q}-H(q,p,t)).$$
3L) Under extremization of the Lagrangian action $S_L[q]$ wrt. the path $q$, the corresponding equation for the extremal path is Lagrange's equation  of motion
$$\frac{d}{dt}\frac{\partial L(q,\dot{q},t)}{\partial \dot{q}}
~=~ \frac{\partial L(q,\dot{q},t)}{\partial q},$$
which is a second-order ODE.
3H) Under extremization of the Hamiltonian action $S_H[q,p]$ wrt. the paths $q$ and $p$, the corresponding equations for the extremal paths are Hamilton's equations of motion
$$-\dot{p}~=~\frac{\partial H}{\partial q} \qquad \text{and}\qquad 
\dot{q}~=~\frac{\partial H}{\partial p} ,$$
which are first-order ODEs.
4L) The equation $p=\frac{\partial L}{\partial v}$ is a definition in the Lagrangian formalism. E.g., for a non-relativistic free point particle, it encodes the relation $p=mv$.
4H) The equation $\dot{q}=\frac{\partial H}{\partial p}$ is an equation of motion in the Hamiltonian formalism. E.g., for a non-relativistic free point particle, it encodes the relation $p=m\dot{q}$.
A: I meant this as a comment to Peter Morgan's answer but it got too long to fit.
For Lagrangians that are quadratic in the generalized velocities $\dot{q}_i$, $i\ldots N$, the $N$ equations of motion obtained by the Euler-Lagrange equations will be second order in time whereas Hamilton's equations of motion for $(q_i, p_i)$, $i\ldots N$ are first order in time. So the number of independent variables are the same. 
As said in the Peter's answer think of the one equation 
$$m \ddot{\mathbf{r}} = \mathbf{F}$$
versus the two equations 
$$\dot{\mathbf{r}} = \mathbf{p}/m, \qquad \dot{\mathbf{p}}=\mathbf{F}.$$
