They don't actually need it.
I realize this is radical, but bear with me. We need to not expect them to be masters of wilderness survival --in all honesty, they aren't. Animals die in the wild all the time. They starve, they freeze, they get lost, they fall in caves and can't get out. That said, they're actually not awful at Survival and the way they're statted reflects that without needing ranks at all.
Let's look at some crunch.
First, I looked at animals and their skill ranks. Animals get 2 + Int mod skill ranks per HD --but because they all have 1 or 2 Intelligence, that modifier is always negative, so effectively animals have 1 skill rank per HD.
Animals have six class skills to choose where to put that one skill rank. Happily PF is nice and gives them a +3 bonus to any class skill they choose to drop it into. But still, giving them another choice seems mean and taunting unless that new skill is really significant to the "animal" concept.
So I turned the question around in my head:
What does Survival do, and is it something animals are expected to accomplish?
DC 10: Get along in the wild. Move [...] while hunting and foraging (no food or water supplies needed).
Nearly anyone can do this by taking ten; I couldn't find anywhere in the PF SRD that says you can't take ten on this use. If you can't take ten, then animals still have a decent chance of succeeding without any ranks. Real animals regularly starve in the wild anyway.
DC 15: Gain a [...] bonus [...] against severe weather.
I can see where animals don't need this as a game mechanic. If a fox freezes, it freezes. Not usually relevant to the game. Real animals regularly perish from exposure.
DC 15: Keep from getting lost or avoid natural hazards.
A wolf in his territory probably doesn't need to make a check for these things. A wolf out of his territory might rightfully be confused. You wouldn't get the awesome dinosaur graveyard that is the La Brea Tar Pits if dinosaurs had more ranks in Survival.
DC 15: Predict the weather.
Elephants and earthquakes aside, this doesn't seem common enough or important enough to justify training. Their untrained 25%-35% chance to anticipate weather probably reflects this pretty well if it's something you want to include in your games.
DC [varies, gets high really fast]: Follow tracks.
This, some animals need to be good at. Others... not so much.
So several of the functions granted by Survival are tangential to an animal's role in Pathfinder --probably so much so that making it a class skill and giving them access to all those abilities with high probability of success is overkill. Besides...
These are low DCs and animals have Wisdom
It's worth noting that most animals have positive Wisdom modifiers, and none to my knowledge have negative Wis mods. This means that even untrained, an animal has a decent chance of achieving the above abilities with their DCs of 10 and 15.
This means that a "lone wolf" (Wis 12, and unusual; wolves should be in packs) eats just a bit more than every other day on average (9 or higher on a d20). He's not even in bad shape until he misses at least two days in a row (at which point the starving rules kick in).
Let's put him in a pack. Most of the wolves use Aid Another for a single check by one wolf, or they all roll individually and the ones who roll high can compensate for the ones who roll low. Since they've got a 60% chance of each being able to feed himself, the pack won't get fat, but they're unlikely to starve: one wolf need only roll 11 to compensate for another wolf's 8.
If you give even 1 rank of Survival to a lone wolf, his chances of eating on a given day rise to 80% and the sad, dismal, starving lone wolf is instead a paragon of health and wonders why he needed that pack anyway.
But what about when something like tracking is vital to an animal's iconic abilities?
Let's look at an example: the wolf
The 2HD wolf puts its precious skill points in Perception and Stealth, and its one solitary feat goes into Perception. Survival is left out in the cold, so how can a wolf track anything with its legendary nose?
Racial Modifiers: +4 Survival when tracking by scent.
This bonus is exactly the same as the bonus he'd have with 1 rank in Survival and a +3 class skill bonus, but it only applies in the situation where a wolf is expected to excel.
Racial bonuses can give an animal a much-needed edge in a specific subset of a skill, when it would be inefficient or inappropriate --and definitely unnecessary-- to give the animal access to the skill's entire set of features.