Okay, let's take a look.
Other
- This article provides a list of vermin to select 'animal' companion from. Note that it actually does not prohibit a non-vermin druid to select vermin companion. Also please note that vermin companion is actually considered magical beast.
- Watchspider is a wonderful magical beast located on page 140 of City of Splendors: Waterdeep, which can serve as animal companion, requiring an effective druid level of 4 or higher. It can also serve as familiar or mount, but that's beside the point.
- While we are at it, Tressym (detailed in *Forgotten Realms Campaign Settings) is permitted to be an animal companion at 1st level, as per Sandstorm, p48. Although it is just an animal, it is the only animal I know with Intelligence of 12, easily smarter than its druid master.
Important note: with a liberal interpretation of Wild Cohort feat you can use the above Animal Companion choice expansions with it. With a more liberal interpretation you can also use some of the expansions below (e.g. feats). Strict interpretation limits you to the list in Player's Handbook, though.
Alternate Class Features
- Complete Mage gives an Elemental Companion ACF. Not exactly Animal Companion (no crazy abilities boost), though. Probably you're better off with Summon Elemental reserve feat.
- Urban Companion ACF gives a familiar which is slightly better than a standard sorcerer familiar and is a magical beast. If it can be used in conjunction with Improved Familiar and other familiar-related goodness, then you are set, I believe.
Feats
- Exalted Companion allows a druid to select from a limited list of magical beasts.
- Beast Totem allows to take Totem Companion - one more list of magical beasts to select from.
- Devoted Tracker allows to select your special mount to be your animal companion, effectively giving you a magical beast companion.
- Vermin Companion allows to select from a limited list of vermin.
- Spider Companion allows to select from a limited list of spiders. Setting-independent, but steep prerequisites and you already can select vermin companions per aforementioned WotC article.
Prestige Classes
- Arcane Hierophant makes his animal companion his familiar, which is treated as magical beast from there on.
Dragon Magazine material
- Monstrous Animal Companion, while requiring yet another feat, allows to select your animal companion from yet another list of magical beasts. 8-headed hydra, anyone?
- Plant Companion alternate class feature (Dragon Magazine 357). Gain a plant companion instead of an animal. I'm afraid I don't know the details of the deal, though.
- Spell Sovereign prestige class (Dragon Magazine 357). Remember Urban Companion? This allows to have living spell as familiar. The details still escape me, I don't own Dragon Magazines.
Third party
Just stumbled upon this.
- Ooze Companion feat. One of the Pathfinder books allows druid to select his animal companion from a list of oozes. Ew.
There may be more.