This is only a partial and working answer until I can look into Cerunnos, Veles, and Shiva.
My first inclination is that this is a case of the Texas sharpshooter fallacy. These four gods have associations with those two animals, and so you posit they must be a related. However, there's no telling when these gods developed these characteristics and whether they're primordial or just highlighting two accidental convergences.
Let's take a look at the Greek side, since I know that best.
First of all, snakes have long been a symbol of immortality. Think of the snake in the Garden of Eden or the Gilgamesh epic who snatch away immortality from Adam and Eve or Gilgamesh, respectively.
In the Iron Age, Dionysus developed a cult of immortality around him, one of the several savior cults around the Mediterranean. The most solid evidence comes the 400s, but it likely developed earlier. Multiple tablets attest to Dionysus' power to rescue souls from the Underworld. This could have given Dionysus his serpentine associations. (Cole, 338ff.)
As far as the bull goes, this is likely Mycenaean in origin and probably predates any the snake associations. Cattle are sacred to Dionyus at Cynathea in Arcadia, which has an unusual feast to him there (from Theoi):
(Pausanias, Description of Greece 8. 19. 2) "The most notable things here [at Kynathea, Arkadia] include a sanctuary of Dionysos, to whom they hold a feast in the winter, at which men smeared with grease take up from a herd of cattle a bull, whichever one the god suggest to them, and carry it to the sanctuary. This is the manner of their sacrifice."
He is also called "bull-faced" in the Orphic hymns, paralleling the epithets for Hera (cow-faced) and Athena (owl-faced, or possibly gray-eyed).
Also, I wouldn't write off Hermes right away. The earliest sources for Hermes after the Odyssey definitely tie him to cattle. In his Homeric Hymn, Hermes steals the cattle of Apollo and then lies about it. He was so clever at it, though, Zeus granted him a position on Olympus. The snake association is actually more tenuous, as the entwined serpents around his staff is rather late iconography, and perhaps comes from Hippocratic symbolism, which in turn developed from the Asclepius cult. (See Wikipedia for a good rundown of the evidence.)
While I haven't looked at the earlier gods, I do think this analysis should lead you to hesitate in positing whether the snake and the bull really do belong together.