Lets say I buy a giant chameleon and want it to have the stable gallop and narrow frame feats.
How do animals (not familiars or animal companions) gain feats, if they do at all?
How do they gain skill ranks?
Can I substitute out it's starting skills/feats for ones I want?
As the other answer points out correctly - generally feats are only gained when you gain hit dice.
However arguably the Cavalier ability Tactician could grant Teamwork feats to a mount, though a GM might rule against it.
More usefully however the feat Animal Ally would allow you to gain an Animal Companion, which will gain hit dice as you level and thus gain feats (note that many feats and skills require an Int of 3* or greater, but the animal companion will gain stat bonuses every 4 levels, just as a character does). http://paizo.com/threads/rzs2ktcl?Animal-Companion-with-3-INT
The Monstrous Mounts section of the leadership feat may also be worth a look.
Familiars generally don't gain feats and generally can't be used as mounts, but they do gain skills. There are exceptions, such as a Beast-Bonded Witch, and feats you can take to improve or evolve familiars. There are lots of different ways to gain familiars - there may be one available to you.
Tecnically, you could Retrain them just like you can retrain your character, as the retraining rules don't specify who can or cannot do it. So they are allowed to everyone, PC, NPC or monsters.
The Handle Animal rules won't cover feats, just tricks.
How do animals (not familiars or animal companions) gain feats, if they do at all?
They only gain feats when their Hit Die are increased. There is absolutely no way for a PC to increase that without making it an animal companion or similar class feature, or without Awakening them. But if awakened, it might not like being your mount anymore.
Can I substitute out it's starting skills/feats for ones I want?
GM's decision, it's his world and he has to say if it's possible to find one that was trained exactly how you wanted it. Just like he can say if a certain town has combat trained horses or not.
Retrain existing, useless feats into useful ones.
Party with the animal in question. Speak with Animals will be useful here. Involve it in combats and stuff so it gets XP. If necessary (e.g. you are a high level) find (or create) artificially low levelled opposition and Power Level it up to speed. Reccomend it take PC class levels instead of Racial HD cause PC class levels are just better. Obviously it should avoid Int-based classes but something like Cleric or Barbarian could work out nicely. If only PCs get PC classes, go for levels in Adept (or Warrior if you're looking for a melee-combat type ally).
Advise it on feat and skill selection in-game during level up periods.
