The rule that says that a dragon "is required to devote a level every few years to its dragon 'class,' reflecting the extra Hit Die or level adjustment it gains from aging" is from the Draconomicon section on Dragons as Player Characters (141-4), and, as such, it doesn't apply to a dragon befriended through the feat Dragon Cohort (104 and 138-9). Thus, like any other cohort, a dragon cohort advances as the DM decides it advances. So such a dragon's advancement, for example, could be exclusively by gaining more racial Hit Dice… or could be by taking levels of commoner so that it can be a dragon of the people! (I recommend the DM have this latter choice be extremely rare and suspect that, in all likelihood, the dragon'll probably advance by taking levels of sorcerer.)
Beyond the dragon-only prestige classes in the Draconomicon, undoubtedly a few others exist in Web articles, magazines, and sourcebooks, but only the prestige class dragon ascendant (90-2) is awesomely better than what a typical dragon gets from having levels in some base classes or even, sometimes, its racial Hit Dice, and that prestige class is quite a ways out of reach of a wyrmling, even a red!
If the need arises to advance quickly a dragon's age category, see Is there a way to make a wyrmling dragon become an adult via anything from any book? To summarize, I recommend a friendly necromancer (oxymoron notwithstanding) cast on the dragon the officially licensed 8th-level Sor/Wiz spell hasten the end [necro] (Holy Orders of the Stars 70) and a friendly cleric follow that spell with the 7th-level Clr spell greater restoration [conj] (PH 272).
The celadrin should work…
The Dragon #350 article "Legacies of Ancient Empires" (50-7) by Eric Boyd describes the celadrin planetouched. They possess the type outsider and the subtype native, have Level Adjustment +1 and no racial Hit Dice, and possess, among other abilities, the racial trait elven blood:
For all special abilities and effects related to race, a celadrin is considered an elf. Celadrins, for example, can use elven weapons and magic items with racially specific elven powers as if they were elves. (52)
While this description of the racial trait elven blood is slightly different from the description found in the Player's Handbook and Monster Manual for Dungeons and Dragons 3.5, it nonetheless aligns perfectly (with appropriate finding-and-replacing, obviously) with the half-elf racial trait elven blood from the Player's Handbook for Dungeons and Dragons, Third Edition! Despite Dragon magazine having converted to 3.5e over forty issues earlier, with such evidence in hand, it should be a small matter to convince the DM to make a minor adjustment that will bring this outdated Third Edition description of the racial trait elven blood up to 3.5e standards.
…And so should the fey'ri…
The planetouched fey'ri (Races of Faerûn 118-21) possess the type outsider and the subtype native, have Level Adjustment +2 (or +3 with damage reduction or the spell-like ability dimension door or enervation) and no racial Hit Dice, and possess, among other abilities, the racial trait elven blood like the aforementioned celadrin and other pre-3.5 revision elflike creatures (hence making some minor adjustments by the DM a necessity).
The Player's Guide to Faerûn Web enhancement "Monster Update" mentions in passing that fey'ri are also tieflings (5). This allows a fey'ri to, for example, meet requirements and feat prerequisites it couldn't've met as just a planetouched fey'ri. That is, a generous DM may allow such a fey'ri to enter the class tiefling paragon (UA 45-6) (for all the good it'll do the fey'ri) or take a feat like Planetouched Animal Affinity (Races of Faerûn 167) (for all the good that feat does anyone).
(A player can ask the DM if this also means that a fey'ri gets, in addition to the typical traits of a fey'ri, the traits of the typical tiefling (Monster Manual 209-10). The DM will probably say No, but a player can ask, and, really, LA +2 is a lot. But, here, just in case, take this helmet, and look out for hurled dice.)
…but other creatures will struggle
While the Epic Level Handbook belabors the creature's closeness to elves, the leShay (202-3), an epic fey with 50 Hit Dice and no supplied Level Adjustment, has the natural ability elf traits that does not seem to enable a leShay to meet elven blood requirements and prerequisites, instead only providing the leShay with minor elf-like features without it actually being an elf. However, with a leShay's fifty fey racial Hit Dice, this DM would seriously consider a house rule granting a leShay the racial trait elven blood. At the typical point at which a leShay is usable as a PC, that's not going to be a big deal.
Keith Baker's Web article "Druids of Khorvaire, Part Four" includes the description of the Valenar warhorse, an animal with 4 Hit Dice, no supplied Level Adjustment, and an Intelligence score of 2 (and, according to Dungeon Master's Guide 172, the DM should not "allow players to play creatures who have an Intelligence score of 2 or lower"). Nonetheless, if the DM is accommodating (maybe the Valenar warhorse is the subject of an awaken effect?), the section Valenar Horses says
Aside from its enhanced speed and Dexterity, a Valenar horse can live for up to ten times the lifespan of a normal horse; the Tairnadal [elves] attribute this longevity to the elven blood they believe runs through the veins of the steed.
(Emphasis mine.) Ask the DM if this belief is true then, if it is, ask if it means a Valenar horse technically meets prerequisites and requirements as if the horse has the racial trait elven blood. (Were this DM to approve such a thing, he would concoct a tale that has an injured Valenar horse in the distant past receiving a field transfusion from his elven master. So you know.)
Note: I made a good faith effort to work my way through this edition's printed Wizards of the Coast material as well as Web material. I did not search extensively issues of Dragon, Dungeon, Living Greyhawk Journal, or Polyhedron nor third party material that bears the officially approved Wizards of the Coast seal. Other options may yet exist, buried in more obscure sources.
Best Answer
Classes, templates, and feats
Surreal's Lists of Stuff mentions—and A_soo's answer describes—many of the classes granting wild shape and its alternatives. (Omitting, for example, the variant totem druid (Dragon #335 87) is totally acceptable: the level 1 supernatural ability totem shape "uses all the same rules as wild shape" but isn't actually called wild shape. Sigh. Good thing that doesn't matter as druid levels are off the table anyway.) KRyan's answer describes the feat Initiate of Horus-Re (CV 31) with its limited wild shape and the template Mulhorandi divine minion with its variant fast wild shape.
In addition, the prestige class shapeshifter (originally Oriental Adventures 45-6 and updated to Dungeons and Dragons 3.5 by the Dragon #318 article "Oriental Adventures Update: Eastern Flavor" (35-6)) grants explicitly and progressively better wild shape starting at level 1. In addition to the requirements base attack bonus +3 and Concentration 10 ranks, a creature needs to meet the special requirement Alternate Form: "Must either know polymorph self or have a natural alternate form, alter self, polymorph self, or shapechange ability" (OA 46). Despite polymorph self not being a spell in 3.5, the update left that untouched; talk to the DM and see if "minor adjustments" (DMG 4) can be made to these requirements (like expanding them!) to bring them in line with the 3.5 revision.
Race
The planetouched race worghest (Dragon #350 56-7) has the supernatural ability change shape allowing it at will to take a standard action to assume the form of a wolf but also allowing it to "take feats requiring the druid's wild shape ability as a prerequisite." This makes available options that should only be accessible to creatures with actual wild shape—like Aberration Wild Shape (Lords of Madness 178) or Bestial Charge (Complete Champion 56)—which might make druids perceive a worghest's already supernatural ability change shape as wild shape. Maybe this is close enough?
While a worghest normally mandates a Level Adjustment of +2, a generous reading of Player's Guide to Faerûn on Variants: Races with Level Adjustments (190-1) lets a planetouched creature change its type from outsider to humanoid (planetouched) to suffer no Level Adjustment, but it's likely only by accident that these rules apply to the worghest, so ask the DM and good luck. Also, like many creatures that can assume other forms, changing from wolf to worghest may be an issue.
Magic items
The Dragon #324 Magic Shop column "Power at a Price" includes the following:
Obviously, this item has problems—it's a little heavy, don't you think?—, but chief among them is that a level 4 druid doesn't have the supernatural ability wild shape; given the skin's drawback, a DM should forgive this oversight and house rule the skin to level 5. If the DM doesn't, the amulet of wild shape (Magic of Faerûn 167) (40,000 gp; 0 lbs.) grants wild shape as a level 5 druid… or increases existing wild shape ability by 4 effective druid levels to a maximum of 20. The amulet's advantage is that it's not limited to once per day like the skin, but the skin's not limited to an effective druid level of 20. O, the skin has the advantage of lower price, too, if that's a concern. (Ask the DM what happens if a creature gains a level while wearing a borrowed skin, takes the feat Extra Wild Shape (Complete Divine 81) (or willfully misreads Fast Wild Shape (CD 81-2)), then returns the skin to its owner. I suspect the creature's head explodes and it dies but results may vary.)
(Combining amulet then skin with the druid's vestment (DMG 268) (10,000 gp; 0 lbs.) and the magic item set trappings of the beast (Complete Champion 135-6 et al. collectively costing over 50,000 gp) lets the wearer use wild shape like a level 10 druid except that it's 6 times per day and that it's usable as a swift action, which is pretty cool, and it had better be cool: the whole shebang costs over 100,000 gp!)