So this is possible.  But depending on how you did it could be quite laborious (IE adding all enemies to specific databses or attaching scripts to all of them).   There are a lot of enemies in the game as you know.  
Two story editor calls can level up a character:
CharacterLevelUpTo
CharacterLevelUp
I'd probably attempt to do it something like this:
IF
DB_CombatCharacters(_Character,_Combat)
AND
NOT DB_IsPlayer(_Character)
AND
NOT DB_LeveledCharacter(_Character)
THEN
DB_LeveledCharacter(_Character);
CharacterLevelUp(_Character);
When characters begin combat, they are added to the DB_CombatCharacters Database by the base scripts.  This includes players however so I put in a check to make sure the character isn't one.  Then I put in a check to see if the character had already been leveled before.  Because if you say started a combat with a character and then fleed and that query wasn't there you'd level up the character every time you started combat with it.  
The one problem with the script I posted above is it levels EVERY character.  I just did it that way to make sure it works, and it does.
So you'd have to run a second statement to randomize it.  There's a query called "Random" which will do just that.  So if you wanted 1 in 4 you set the Parameters of the random query to be a range of 0-3, and when the random integer =='s 3 it does the level up.  But if it =='s 0-2 it doesn't.  Then it still adds them to the database so they don't get a second bite at the apple of leveling up.
The negative of doing it the way I showed above is you'd see the characters level up in front of you.  But I think that's a small price to pay to avoid attaching scripts to every NPC or cataloging them in a DB manually beforehand. 
You could also do it with a combination of character and story scripting which might be a bit more elegant, but again laborious.  
You could also use this same approach to implement level scaling by checking the player character's level and upping the enemy to match.