I think, if you assume a flat surface, nothing would physically prevent a bicycle being ridden, slowly, on Deimos.
In particular friction is not a problem: friction limits the amount of force the tyres can exert on the ground, but the force you need is extremely low if the acceleration you need is extremely low, which it is. Riding a bicycle is something where things scale with $g$: a bicycle can be ridden for any value of $g > 0$, you just have to ride it with acceleration (and, ultimately, speeds, if you don't want to reach escape velocity on the surface) which scale like $g$. This is all perfectly possible.
I think the problem would be getting a human to do this. We have spent a long time evolving for life on a planet where the $g \approx 9.8\,\mathrm{m/s^2}$ so we've evolved around the kinds of forces, powers and time constants to allow us to walk (and ride bikes) on Earth. To do it on Deimos you'd have to wind all this back by a huge factor, which would mean that a lot of things we do unconsciously in fractions of a second you would now have to do consciously over many seconds. My guess is humans would find that extremely hard. Perhaps robots could be taught to ride bikes on Deimos (pretty sure there's a science-fiction story here...).
On the other hand people can learn things pretty well, and there's plenty of time: the time taken for things to happen scales like $\sqrt{1/g}$, so if you assume you need to correct things on Earth in a fifth of a second to ride a bike, then on Deimos you'd have around ten seconds to think. The problem would be suppressing your reflexes. So I'm not willing to conclude humans couldn't do it, just that it might be hard.
Of course, in real life the surface is not smooth which would make things much more exciting. And also riding a bike would be really slow, especially on a non-smooth surface: if you wanted to get anywhere quickly better to jump.
One argument which is not true is that you couldn't ride a bike because bikes are stabilised by the gyroscopic forces from the wheels. They may be, but what is certainly the case is that humans can hold a bike up while it is effectively stationary (this is much easier, and may only be possible, if the bike is facing up a hill, or has no freewheel), so you can ride bikes with no gyroscopic help.