I've had several cities rebel, when they had full garrisons (ie at least as many as the required number). I think though that in each case they were out of food. Is there an extra chance of rebellion if the city is starving, or do the garrison units not count anymore when they get to zero morale.

Running out of food has the exact same effect as not having enough garrisons, or in your words, the garrisons simply don't count when the city reaches zero food. It doesn't have anything to do with morale though - the city starts rebelling the second it runs out of food, and stops the moment you deliver some food to it (provided enough garrisons are also present).

Sending in whatever units you have nearby with the food they carry usually solves this problem until you can sort out the supply. And it's often worth keeping garrisons who consume the least food, even if they're more expensive - e.g. in cities which required 35-40 garrisons I kept a regular 40-man hoplite brigade instead of 2 spearmen companies.

Thanks, good tip about the Hoplites