I'm looking for a way to have an Animal Companion with classes other than Druid or Ranger, for example a Paladin that fights with a trained hawk. I'm all for multiclassing if need be, but I'm looking for other ways as well, through feats if necessary. I'm not really worried about min/max stats or optimized builds.
There is a plethora of classes that either have an Animal Companion as a class feature by default, or can gain one via Archetypes.
In particular, the Huntmaster Cavalier comes pretty close to your idea of a Paladin with a Hawk, albeit without the inherent holyness that a Paladin has.
Alternatively, if you want to keep the clerical aspects of the Paladin, rather than the knightly ones, a Sacred Huntsmaster Inquisitor might be worth looking into.
The following list is limited to Paizo content and not exhaustive, particularly towards the end (I didn't actively look for Archetypes that grant a mount, for example)
Standard classes with Animal Companion
Druid, the iconic AC class.
Rangers can get an AC via Hunter's Bond, at lvl-3.
The Hunter from the ACG is a Druid-Ranger-Hybrid, with a uniquely strong focus on the animal companion.
Cleric, via Animal Domain (or it's subdomains Feather and Fur), at lvl-3
Classes with Archetypes or Options that grant Animal Companions
Barbarian, Mad Dog: Gains Improved Drag and can use it as swift action to pull an enemy toward his master.
Ranger, Falconer: bird only, full effective level, can learn special trick.
Alchemist, Winged Marauder: Dire Bat or Giant Vulture only
Cavalier, Huntmaster: Bird or Dog companion, can benefit from the Cavalier's Tactician ability, gains extra effect on it's attack.
Inqusitor, Sacred Huntsmaster: gains master's Teamwork feats automatically.
Oracle, Lunar Mystery, Primal Companion revelation: bear, boar, crocodile, shark, tiger, or wolf.
Brawler, Wild Child: learns the same Combat maneuvers as its master.
Classes and Archetypes with features that "function as a druid's animal companion"
Paladin: Divine Bond can be a mount.
Cavalier: Mount class feature.
Bloodrager, Bloodrider: gains a Feral Mount at lvl-4.
Shaman of Nature or Mammoth Spirit can have thier familiar gain the physical aspects of an animal companion - albeit at level 16, BUT, with the bonus of still being able to use familiar abilities. Mammoth spirit does have to be a megafauna companion, though.
Many, many classes have an archetype that grants an animal companion or other special access to them. However, failing that, any character of at least level 4 may gain access to an animal companion via the Animal Ally feat, though most characters may have to wait to level 5 (the next feat level in pathfinder) to actually take the feat.
In the specific case of a paladin, you must delay access to the Divine Bond ability by one level (probably by dipping a level of cleric or some such) in order to be eligible for the feat. You could also give up the mount from that ability for the weapon option, but if you choose the mount option your hawk (or whatever) has an effective druid level of (your total level including your paladin levels)+(your paladin levels again)-3, which is pretty cool. At level 6 this is the difference between an EDL 8 hawk and an EDL 3 hawk, which is a sufficient difference to necessarily alter how you use it in game.
Consider also that not all animals you use in combat or otherwise need to be animal companions. Animal companions are special super-powerful bonded animals that you pretty much control directly. You can get a loyal, useful, hunting hawk by training one with the Handle Animal skill. If you want a normal hawk to use for rabbit hunts and message delivery, this is probably more appropriate. If you want your hawk to scout out the enemy troop movements and report back, the animal companion version is a better bet.
A wildblooded sorcerer with the sylvan bloodline gives you an animal companion level -3.
With the appropriate robe that rise your sorcerer level by 4 concerning your bloodline powers, it could end up one level above your sorcerer level.
Also if you are human, with the Huntmaster feat you are treated as one level higher when determining the abilities of your animal companion or mount, as long as it is: bird, dog, small cat, or horse.
The Advanced Class Guide's Hunter has class abilities that specifically pertain to improving your animal companion and having it fight alongside you as a friend and teammate. One notable Hunter archetype is the Packmaster, which grants your character the ability to have multiple animal companions.
The Inquisitor archetype Sacred Huntsmaster grants your character an animal companion as well.
You can also get an animal companion via the Animal Domain. Your effective druid level for this animal companion will be equal to your cleric level -3.