Let's say there's a field that acts perpendicularly to the direction of velocity of a particle (& it does not depend on the speed; it's a constant force) and hence does no work. Would this field be conservative?
The work done by this field along a closed loop would be zero but I don't see how potential would be defined for this field since it does zero work.
No, it would not because conservative forces, by definition depend only on the position. Your force should depend also on the velocity (its direction) because it is perpendicular to it.
Forces whose work is always zero are not necessarily positional so that they are not necessarily conservative. There are two important cases in elementary physics: Coriolis' force and magnetic force.
For these forces no potential energy can be defined so that non energy conservation theorem can be formulated (where these forces give some contributiin).
In more advanced formulations of mechanics a generalized notion of potential can be introduced that depends also on the velocities, but there is not necessarily a theorem of total energy conservation (there is if further hypotheses are true and is called Jacobi's theorem).
A force $\vec F$ is to be considered conservative, if it does no work along a closed trajectory,
$$\oint_C \vec F(\vec r)\cdot \mathrm d \vec r=0$$
where $C$ is a closed curve. You can intuitively think of a particle moving with $\vec v$ along a circle in $\mathbb R^2$, such that $\vec F \bot \vec v$. So $\vec F$ points to the center of the circle. On the top point of the circle, $\vec F$ points straight downwards, while at the bottom point of the circle, $\vec F$ points straight upwards. This means, for two opposite points on the circle the work done by $\vec F$ has opposite sign and therefore cancels out. So the above stated condition holds.
The potential $\Phi$ of $\vec F$ is not defined through the work done by $\vec F$. A scalar potential $\Phi$ of a force $\vec F$ is defined by the differential equation
$$\vec F(\vec r)=-k\vec \nabla \Phi(\vec r)$$
here $\vec \nabla$ is the gradient of $\Phi$.
As an intuitive example, you can check that the gravitational force
$$\vec F = - \frac{G m M}{r^2} \vec r$$
has a potential
$$\Phi = - \frac{G m M}{r}.$$
This is done by integrating $1/r^2$ and setting $k=-GmM$.
OP's force would not be a conservative force in a traditional sense because of the velocity-dependence. For a discussion of the notion of conservative forces, see e.g. my Phys.SE answer here.
It is interesting to ponder whether a force of the form $$ {\bf F}~=~f(v^2) {\bf v} \times {\bf B}({\bf r},t) \tag{1}$$ could have a velocity-dependent generalized potential $U=U({\bf r},{\bf v},t)$ so that $$ {\bf F}~=~\frac{d}{dt} \frac{\partial U}{\partial {\bf v}} - \frac{\partial U}{\partial {\bf r}} ~?\tag{2} $$ Here $f=f(v^2)$ is a function that may depend on the speed square $v^2\equiv {\bf v}^2$. If $f(\cdot)=1/\sqrt{\cdot}$ is an inverse square root, then the force (1) would be an example of OP's form. Unfortunately, one may prove that the force (1) only has a generalized potential $U$ if $f$ is a constant function. The constant case corresponds to the Lorentz force, see e.g. my Phys.SE answer here.
