I put together some rules for introducing monsters several levels before they normally show up, but keeping them about the same level of toughness. I haven't quite finished the experiment by doing a Normal to Solo upgrade (which would also jump 9 levels), but I've got Normal to Elite (-4 levels) and Elite to Solo (-5 levels). When using these (and when using any monster at all), do keep an eye on the final result and tweak to fit your group.
Elite-Normal Template
This template is used when you wish to have a creature appear several levels before it normally does, but still retain much of its expected toughness. This is particularly useful when converting existing modules or when setting a progression of difficult with a creature showing up as elite early on, normal several levels later, then eventually minions. Be aware that the DM’s Toolbox rules for raising and lowering levels may be adequate for your purposes by lowering the level of a creature without also making it an elite. While the template reduces level by 4, feel free to then apply the normal level up and down rules from the DM's Toolbox from there.
Level -4
Attacks All -4
Defenses All -2
Saving Throws +2
Action Point 1
Hit Points As appropriate for an elite of that level (see DMG p184)
Other Modifiers Reduce skill modifiers, ability check modifiers, and initiative by 2
Powers:
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Action (Immediate Reaction, when bloodied)
The creature gains an action point and immediately uses it to gain a standard action. See also action mastery.
Note that damage should not change from the base creature.
Examples:
Minotaur Warrior
Level 6 Elite Soldier
Medium natural humanoid
XP 500
Initiative +5
Senses Perception +12
HP 148; Bloodied 74; see also bloodied action
AC 24; Fortitude 25, Reflex 19, Will 21; see also action mastery
Saving Throws +2; see also action mastery
Speed 5
Action Point 1; see also bloodied action
Battleaxe (standard; at-will) * Weapon
+12 vs. AC; 1d10 + 6 damage, and the target is marked until the end of the minotaur warrior’s next turn.
Goring Charge (standard; at-will)
The minotaur warrior makes a charge attack: +13 vs. AC; 1d6 + 6 damage, and the target is knocked prone.
Ferocity (when reduced to 0 hit points)
The minotaur warrior makes a melee basic attack.
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Action (Immediate Reaction, when bloodied)
The creature gains an action point and immediately uses it to gain a standard action. See also action mastery.
Alignment Any
Languages Common
Skills Dungeoneering +10, Intimidate +9, Nature +7
Str 23 (+9) Dex 10 (+3) Wis 14 (+5)
Con 18 (+7) Int 9 (+2) Cha 13 (+4)
Worg
Level 5 Elite Brute
Large natural magical beast
XP 400
Initiative +5
Senses Perception +7; darkvision
Frightful Growl (Fear) aura 3; enemies in the aura take a -1 penalty to attack rolls, and allies in the aura gain a +1 power bonus to attack rolls.
HP 160; Bloodied 80; see also bloodied action
AC 18; Fortitude 18, Reflex 16, Will 16; see also action mastery
Saving Throws +2; see also action mastery
Speed 8
Action Point 1; see also bloodied action
Bite (standard; at-will)
+8 vs. AC; 2d6 + 5 damage, and ongoing 5 damage (save ends).
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Action (Immediate Reaction, when bloodied)
The creature gains an action point and immediately uses it to gain a standard action. See also action mastery.
Alignment Chaotic Evil
Languages Abyssal
Skills Stealth +10
Str 21 (+7) Dex 17 (+5) Wis 10 (+2)
Con 20 (+7) Int 7 (+0) Cha 16 (+5)
Solo-Elite Template
This template is used when you wish to have a creature appear several levels before it normally does, but still retain much of its expected toughness. This is particularly useful when converting existing modules or when setting a progression of difficult with a creature showing up as solo early on and elite later on. Be aware that the DM’s Toolbox rules for raising and lowering levels may be adequate for your purposes by lowering the level of a creature without also making it a solo. While this does reduce the creature's level by 5 as part of turning it into a Solo (keeping the XP value the same), you can then raise or lower the creature's level as normal after the template is applied.
Level -5
Attacks All -5
Defenses All -3
Saving Throws +5 Total
Action Points 2 Total
Hit Points (8 * (NewLevel + 1) + Con) * (4 if Heroic, otherwise 5)
Reduce skill modifiers, ability check modifiers, and initiative by 2
Powers
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Frenzy (when first bloodied)
The creature recharges all powers and gains a +2 to attack for the encounter. It also gains an action point and may immediately use it to gain a standard action. See also action mastery.
Note that damage should not change from the base creature.
Examples:
Manticore
Level 5 Solo Skirmisher
Large natural magical beast (mount)
XP 1,000
Initiative +10
Senses Perception +11
HP 260; Bloodied 130
AC 23; Fortitude 21, Reflex 21, Will 19; see also action mastery
Saving Throws +5; see also action mastery
Speed 6, fly 8, overland flight 10
Action Points 2; see also action mastery and bloodied frenzy
Claw (standard; at-will)
+10 vs. AC; 2d6 + 5 damage.
Spike (standard; at-will)
Ranged 10; +10 vs. AC (see also guided sniper); 1d8 + 5 damage. Hit or Miss: The Manticore shifts 3 squares after making the attack.
/
Manticore’s Fury (standard; at-will)
The manticore makes a claw attack and a spike attack (in any order) and may shift 1 square between the two attacks.
Spike Volley (standard; recharge
)
Area burst 1 within 10; +10 vs. AC (see also guided sniper); 1d8 + 5 damage.
Guided Sniper (while mounted by a friendly rider of 10th level or higher; at-will)
A manticore with a rider gains a +2 bonus to attack rolls with its spike attack and spike volley power.
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Frenzy (when first bloodied)
The creature recharges all powers and gains a +2 to attack for the encounter. It also gains an action point and may immediately use it to gain a standard action. See also action mastery.
Alignment Chaotic Evil
Languages Common
Skills Stealth +13
Str 21 (+8) Dex 20 (+8) Wis 17 (+5)
Con 17 (+6) Int 4 (+2) Cha 12 (+4)
Note: It'd be reasonable to lower the level requirement on Guided Sniper.
Grell Philosopher
Level 6 Solo Controller
Large natural magical beast
XP 1,200
Initiative +8
Senses Perception +10; blindsight 12
HP 288; Bloodied 144; see also bloodied frenzy
AC 24; Fortitude 18, Reflex 21, Will 20; see also action mastery
Immune gaze; Resist 20 lightning
Saving Throws +5; see also action mastery
Speed 1 (clumsy), fly 6 (hover)
Action Points 2; see also action mastery and bloodied frenzy
Tentacle Rake (standard; at-will) * Poison
Reach 2; +12 vs. AC; 3d8 + 5 damage, and the target is slowed and takes a -2 penalty to attack rolls (save ends both).
Lightning Lance (standard; at-will) * Lightning
Ranged 10; +9 vs. Reflex; 3d6 + 6 lightning damage, and the target is blinded (save ends).
Psychic Storm (standard; recharge
) * Psychic, Zone
Area burst 2 within 10; +9 vs. Will; 3d8 + 3 psychic damage, and the target is dazed (save ends). The psychic storm is a zone that lasts until the end of the encounter. Any creature entering the zone is dazed (save ends).
Venomous Mind (standard; at-will) * Psychic
Close burst 3; targets enemies; +10 vs. Will; 2d8 + 5 psychic damage and the target must choose a random target for any melee attacks it makes (save ends).
Action Mastery
When the creature spends an action point, it gains a +4 bonus to any attack made during the action granted by that action point, may make a save against any harmful effects a save can remove as a free action, and gains a +2 bonus to all defenses until the end of its next turn.
Bloodied Frenzy (when first bloodied)
The creature recharges all powers and gains a +2 to attack for the encounter. It also gains an action point and may immediately use it to gain a standard action. See also action mastery.
Alignment Evil
Languages Deep Speech
Skills Arcana +11, Stealth +18
Str 14 (+5) Dex 21 (+8) Wis 14 (+5)
Con 16 (+6) Int 16 (+6) Cha 13 (+4)
And finally, an example of me taking these rules and then modifying the final result - the owlbear is just too bursty on a single target when decreased and I would have altered the result of a standard Owlbear reduced 5 levels in the normal way too.