How does an electrolyte conduct electricity at low potential?
Under low potential differences, electrolytes conducts electricity in a similar way that they does at high potentials differences. I think, after reading the question and the comments, that the key point to understand this is: electric potential difference between which spatial points?

The conductivity of a solution is measure of its ability to conduct electricity when the solution is under a difference of electric potential. That is: the solution must be under the influence of an electric field (remember that $\boldsymbol E = - \nabla \boldsymbol \phi$) for having a non zero flux of charges.

You have to look the potential differences inside the solution and not at the electrodes.

You are right in that in order to maintain for long time a continuous current  electrolysis is required (at least for simple experimental devices). If there is not electrolysis you won't see a current. However, this is not because the solution (lets say the bulk, that is where the solution as such is (homogeneous)) does not have the ability of conduct electricity, but because there would not be a net external electric field at all in that region.

In short, the conductivity of the solution is not dependent of your ability for creating an external electric field on it.

EDIT


  But then again, what if the potential difference passes a treshold and
  at a certain point allows electrolysis, wouldn't the conductivity
  increase very steeply at that point?


If the potential difference between electrodes is low enough to ignore electrolysis, then there will be a charge accumulation in their surroundings that generates a contrary effect in the potential of the solution "far" from electrodes. So, the mean electric field in the bulk will be null.

According to Ohm's law:

$$ \boldsymbol J = \sigma \, \boldsymbol E$$

For the reasons stated above: $\boldsymbol E = \boldsymbol 0$, and so $\boldsymbol J = \boldsymbol 0$. What is the value of $\sigma$ for the solution? As any value satisfies the equation: We can say nothing from Ohm's law
! (technically, it can be computed even if no electric field is present, but it is not important here).

If the potential allows electrolysis, then a current appears so in principle you can measure the conductivity of the solution using Ohm's law. Notice that it is not an step function the current vs. potential. Due to this, there is not a truly step, but it seems because the growing is almost exponential, so we do not notice the increment till we notice a big increment. You can check out the Butler-Volmer equation for more details.

Once the current due to migration (allowed by electrolysis) is measurable, you could measure the solution conductivity. BUT it is a very bad idea, as normally the solutes concentrations are very small and the process of electrolysis change them! (and of course, many times (but not always) we want to know the conductivity to estimate concentrations)