Going off of Keith's original thought:
Start with: -X% to Enemy Health, -Y% to Enemy Speed, -Z% to Enemy Damage
Then: For EVERY ROOM entered the first time + Enemy Health, Speed, and Damage.
Possibly throw in full map knowledge as an early perk.
Something even more AIW-like, though with a major drawback:
1) You can leave normal (non-boss/miniboss/condemend) rooms without clearing them.
2) Any XP gain is deferred until the room is cleared (if you never clear it, you never get XP for killing that room's monsters).
3) The "every room" penalty in ptarth's idea instead is applied when you clear a room.
4) Give
really good perks. Like "MkIV Scout" (reveal all floors) at an early level; multiple marks of "Gravity Turrets" (reduce enemy speed); "Max Armor" (reduce all enemy damage by 80%). MkI Nuke (gives you a consumable that, well, nukes the room, but also adds to the "AIP" penalty like you cleared a room). If you can implement a good photon lance weapon (huge reload time, fixed angle once fired, but is almost unstoppable) that would be a good one for a later level perk.
To summarize: Gaining xp is both very helpful and very dangerous, and you can guerrilla your way through the floors.
The main drawback is that allowing leave-before-clear permits all kinds of cheese. Ducking out mid-fight to regenerate shields, etc.
But, I respectfully submit, that cheesiness would be the
most AIW-like thing about it