Does the conservation of $\frac{\partial L}{\partial\dot{q}_i}$ necessarily require $q_i$ to be cyclic? If a generalized coordinate $q_i$ is cyclic, the conjugate momentum $p_i=\frac{\partial L}{\partial\dot{q}_i}$ is conserved. 
Is the converse also true? To state more explicitly, if a conjugate momentum $$p_i=\frac{\partial L}{\partial\dot{q}_i}=C_1\tag{1}$$ is conserved, will $q_i$ be necessarily cyclic? If we integrate $(1)$, we get $$L=C_1(q_i,\dot{q}_i)\dot{q}_i+C_2(q_i) q_i\tag{2}$$ From $(2)$, it is evident that the conservation of $p_i$ does not necessarily imply $q_i$ is cyclic. $q_i$ is cyclic only if $C_2=0$ which is only a special case.
Assuming my little observation is correct what is an example (perhaps a physical one) of such a situation i.e., a conserved $p_i$ with a non-cyclic $q_i$? I cannot immediately think of one.
 A: THEOREM. Assume that $L(t,q, \dot{q})$ is jointly $C^2$ in the considered coordinate patch and the Hessian matrix  of coefficients $\frac{\partial^2 L}{\partial q^r \partial q^s}$ is everywhere non-singular.
Then, $p_k$ is a constant of motion (it is constant along every solution of EL equations) if and only if $q^k$ is cyclic ($\frac{\partial L}{\partial q^k}(t,q,\dot{q})=0$
for every choice of $t,q,\dot{q}$).
PROOF. If  $L(t,q, \dot{q})$ is jointly $C^2$ and the Hessian matrix  of coefficients $\frac{\partial^2 L}{\partial q^r \partial q^s}$ is non-singular, then for every choice of initial conditions $(t_0, q(t_0), \dot{q}(t_0))$ there is a  local  solution of EL equations satisfying those initial conditions (requiring for instance $C^3$ this solution turns out to be maximal and unique).  Let us pass to the main statement.
If $\frac{\partial L}{\partial q^k}=0$ for every $(t, q, \dot{q})$, then every solution
$t \mapsto (t, q(t), \dot{q}(t))=:\gamma(t)$
of EL equations
$$\frac{d}{dt}\left( \frac{\partial L}{\partial \dot{q}}|_{\gamma(t)}\right)= \frac{\partial L}{\partial q^k}|_{\gamma(t)}\:, \quad \frac{dq^k}{dt}|_{\gamma(t)} = \dot{q}(t)$$
satisfies
$$\frac{dp_k|_\gamma(t)}{dt}=\frac{d}{dt}\left( \frac{\partial L}{\partial \dot{q}}|_{\gamma(t)}\right)=0$$
so that $p_k$ is a constant of motion.
Vice versa, if for every solution $\gamma$ it holds
$$\frac{d}{dt}\left( \frac{\partial L}{\partial \dot{q}}|_{\gamma(t)}\right)=0\:,$$
form EL equations we also have that
$$\frac{\partial L}{\partial q^k}|_{\gamma(t)}=0\:.$$
To conclude, fix a kinetical state $(t,q,\dot{q})$. We know that there is a solution of EL equations which admits that state as initial conditions. Therefore, evaluating $p_k$ along that solution at time $t$,
$$\frac{\partial L}{\partial q^k}(t,q,\dot{q})\left(=\frac{dp_k|_\gamma(t)}{dt}\right)=0\:,$$
for every choice of $t,q,\dot{q}$.    $\Box$
A: *

*The title question (v2) fails e.g. for static Lagrangians $L(q)$ independent of $\dot{q}$. 

*More generally, the title question essentially asks about the possible existence of an inverse Noether theorem, see e.g. this Phys.SE post.

*One cannot naively integrate on-shell equations $\frac{\partial L}{\partial \dot{q}^j}~\approx~c_j$ to deduce an off-shell Lagrangian $L$ (even if $L$ is known to exists). 

*Still not convinced? Try to work out what happens in the case of a free non-relativistic particle.
