Use the Euler-Lagrange equations (motivated in a previous post of mine). These are
$$ \partial_x L - \frac{\mathrm{d}}{\mathrm{d}t} \left( \partial_{v_x} L \right) = 0 $$
We therefore need
$$ \partial_x L = -q \partial_x \Phi + q \left( \partial_x A_x v_x + \partial_x A_y v_y + \partial_x A_z v_z \right) $$
$$ \partial_{v_x} L = m v_x + q A_x $$
$$ \frac{\mathrm{d}}{\mathrm{d}t} \left( \partial_{v_x} L \right) = m \dot v_x + q \dot A_x $$
Putting this all together into the first equation and adding $\dot v_x m$ gives the equation for which you are looking.
Note especially that each component of $A$ is a function of all three coordinates: $A_i = A_i(x,y,z)$; the same goes for $\Phi = \Phi(x,y,z)$ (where usually $A_0$ is identified with $\Phi$ in relativistic electrodynamics).
OP wrote(v1):
What would happen if I considered a system in which the potential is [velocity-dependent] $U(q, \dot q)$?
Well, if OP already knows that the generalized force$^1$
$$\tag{1} Q_j~=~\frac {d}{dt} \frac {\partial U}{\partial \dot q^j}- \frac {\partial U}{\partial q^j}$$
is given in terms of a velocity-dependent potential $U=U(q, \dot q, t)$, this means that Lagrange's equations
$$\tag{2}\frac {d}{dt} \frac {\partial T}{\partial \dot q^j}- \frac {\partial T}{\partial q^j}~=~Q_j,$$
can be written as
$$\tag{3}\frac {d}{dt} \frac {\partial L}{\partial \dot q^j}- \frac {\partial L}{\partial q^j}~=~0, \qquad L~=~T-U.$$
As long as one has Lagrange's equations (3), then it is still true that if $q^j$ is a cyclic coordinate $\frac {\partial L}{\partial q^j}=0$, then its generalized momentum conjugate $p_j:=\frac {\partial L}{\partial \dot q^j}$ is a constant of motion.
$^1$ Here we consider for simplicity a system with only one type of generalized force. In practice, there may be several types of forces (e.g. gravity force, Lorentz force, etc.). The generalization is straightforward.
Best Answer
No, (generalized) velocity dependent potentials $U(q,\dot{q},t)$ do not exist for all (generalized) forces $Q_j$. See e.g. this Phys.SE post.
Even if no variational formulation exists, one may still consider Lagrange equations, cf. e.g. this Phys.SE post.