Interesting fiends...
Anyway, I am working on a demon generator, inspired by the hordlings in Dungeon magazine.
One idea for it is that for every HD the demon has, it is allow to select an ability from one of the following categories: Defense (increased AC, SR, energy resistance,immunities, uncanny dodge, damage resistance), Special physical attacks (additional natural attacks like gore, bite, trample, pounce, rake, rend, improved grab, poison claws, bites, etc), supernatural abilities (frightful presence, breath weapon, gaze weapon), spell-like abilities (self explanatory, although lower HD demons have access to lower level spells and spells of higher level are limited to a number of uses a day, access to certain psionics may be possible), miscellaneous (enhanced senses like see invisible objects, scent, racial skill bonus, bonus feats, etc), enhanced ability scores, gain a subtype (fire, ice, water, etc).
The demon may also take a weakness, like vulnerability to some form of attack, or a penalty in one of its ability scores, in return it gets to select an ability from the above categories.
That's it for now....gotta go to work!