No clue for the realistic regeneration (I think there's got to be a lot of handwaiving involved, especially for the regeneration speed that produces an entire head within minutes). But you can get a multi-headed creature through birth defects.
So, basically your Hydra is a long-necked lizard/dinosaur creature. Size-wise, you've got your choice since dinosaur size could cover anything you want from one-foot tall all the way up to ten-foot shoulder height. And when you've got the embryonic cell division faulty, you could get siamese hydra-twins. Sharing a body, but having multiple heads/necks. It is very possible that the Hydra species has a genetic predisposition for such siamese birth defects, with the conjoined-body - separate-head one most prevalent.
Of course, a nine-headed hydra would then be a real miracle where you will probably need to make use of your enhanced Hydra-regeneration to make such a disposition survivable (I don't want to think about the additional strain on the heart to pump blood not up one long neck only, but 9 necks including 9 very resource-hungry brains). And, as a side-effect, you'd have all kinds of Hydra head-counts, from one or two heads (most of the Hydra population) all the way up to 9 (or more, if you are feeling inventive and generous with the regeneration boost). And one-head-eight-legs hydras. And Hydras with multiple tails or eyes or multiple anything.
So the question remains why such a siamese-twin-prone species didn't get erased by evolution before they even started to become a species? Well, regeneration might be the key factor here. If it is coupled with the siamese-twin-propensity, that would be a deciding factor -- regeneration enhances its biological fitness so much that it offsets the siamese twin defect that comes with the regeneration boost. Since the super-regeneration must have something to do with enhanced cell division, it might already kick in in an embryo and cause all kinds of trouble there -- most notably preventing a full twin from forming (splitting of the embryo) and instead growing back together even before the split was complete. Ergo: siamese twin hydra.