What about a hybrid spells approach that melds at-will wildshaping with more powerful abilities and simultaneously lets the druid focus on wildshaping or standard spellcasting as desired? I'm a bit inspired by 3.5's reserve feats while adopting a more 4e-like approach to how function and flavor meet, which I think much better serves the creative possibilities of wild shape.
Perhaps a druid reserves spell slots to power various at-will abilities, and the shape actually adopted can be a combination of those reserved spells. For example, suppose a 5th level druid reserves two 1st-level spell slots for a terrestrial and an aquatic (w/o waterbreathing) base form with fairly benign stats or stat bonuses. He might also reserve a single 2nd level spell for enhanced speed, and a 3rd level spell for a powerful scent ability. He can then wildshape into a basic form using any combination of those effects, and call the form whatever feels appropriate. A form with all 4 of those effects might be something like an otter, with both terrestrial and limited aquatic abilities. (Although the total number of active forms should probably be limited somehow. Maybe 1 at first level, scaling up to something like 6 or 7 at 20th.)
For forms that deviate from recognized animal types the druid might adopt "wild forms" that are merely animal-like, rather than treating existing animals like a straightjacket. That could inform a role-playing angle, where a villager might see only a new scary animal, while someone skilled in nature lore might have an inkling of something strange afoot. The player should have to describe the basic form of the creature. If they want to make a flying wolf, though, that is fine by me. Just because nature didn't make one (according to current splat books, natch) doesn't mean nature couldn't.
Now, the idea is that these at-will forms are flexible but not particularly powerful. However, suppose one could expend the spell slots of a form to turn into a "paragon" or "dire" version of the animal? Each of these slots could have this paragon version listed with it, which might grant increased size, ability score boosts, etc. Scent might become something like blind-sight, for example. This form would be shorter-lived, and would of course effectively expend some of the at-will flexibility later in the day.
I could also imagine this being compatible with a very minor form of natural casting that would not cause druidzilla. Namely, while wildshaped a druid could "cast" these spells to add to or alter its current form, possibly adding paragon features if needed. For example, suppose a druid were in an at-will wolf form (terrestrial base, extra speed, scent), he might be able to turn into the paragon version of his existing form or add another ability to his existing form. They could even be mixed-and-matched: maybe in some form the druid really needs the paragon version of scent for a few minutes, he could use that in the present form without losing his other at-will abilities.
This scheme would allow a druid to focus on wild-shaping vs. spells in almost any combination. Some would go for flexibility and primarily stick to at-will forms, others would choose the same forms as spells several times in order to use the paragon versions many times a day, while still others would forego it entirely or be content with just a single at-will squirrel wildshape. The balance could change daily, leaving it as a playstyle issue. In addition, by leaving the precise form each version represents vague while more carefully defining the mechanical benefits we let players be creative with the cosmetic aspects without sacrificing mechanical balance entirely. It also avoids requiring a new spell for every single animal.
As an aside, a similar idea could be imagined for animal companions, familars, etc. I'm less excited about it for animal companions because non-spellcasters should be able to get those too, but for familiars I think it could work quite well. The triumphant return of Call Familiar? A wizard with a pseudodragon might be a genuine cause for concern.
Edit: Thinking about the action economy I think it could be quite interesting as well. Let a druid add or swap a characteristic as part of an action, or change any number of characterstics as an action. Complex forms could evolve slowly while doing other stuff, or very quickly if needed. To me the idea of a druid in wolf form jumping off a cliff while swapping (as part of the action) its terrestrial form for an aerial form sounds awesome.