Yes, it's possible to use Zombies, Run! if you're on a bicycle. It'll still be able to track your route via GPS (but not Step Counting) and you'll still hear the story and music. However, depending on your speed, you may be travelling too fast on your bike for the chases!
Remember, it's extra important to pay attention to the road when you're cycling, especially if you have headphones in.