Like ccexplore, I'm concerned about the possibility of level designers making levels that require these features to be used extensively. I guess that's inevitable at any rate though. At least we can discourage such levels by not playing them or giving them bad reviews
A few specific thoughts from me:
Savestates: I tried using these in Lemmix and found it quite awkward. It might just be that the two keys you have to press (ctrl+f1) are far apart on the keyboard, but I prefer to use replays, frameskip and fast forward to retry something.
Rewind: I think this would feel a bit strange to use. I like the idea of keeping a list of moves though.
Text-editing replays: I would consider this to be against the "spirit of the game". I think we should give the player as much control as possible while playing the level, but taking that beyond the level just doesn't seem right. With all the other features mentioned here, it will probably be unnecessary anyway.
Highlight: This was very good to have in L3 where the skills were associated with particular lemmings rather than a global pool, but it could be useful in L1 for keeping track of lemmings with permanent skills. I think this would be preferable to prioritising these lemmings, because sometimes you'll want to select them and sometimes you'll want to avoid selecting them. And if you have a higher priority lemming in the same spot (one that is using another skill, or has a different permanent skill), then the lemming you want could become unselectable even with the option to right-click to select the lowest-priority lemming. A highlight option, with the ability to cycle through lemmings and details of the abilities of the highlighted lemming, would ensure that you can always select the right lemming when you need to. Also, rather than cycling through lemmings, you could have a list of lemmings and choose one to be highlighted, to speed things up when choosing from a big group.
Priority orders: I had the idea that a blocker could be assigned a skill like any other lemming, and unblocked by giving another blocker skill, to make them more dynamic. Under this system, the blocker would have the lowest priority for every skill, so you won't unblock it by accident, and you can only select it with a single click if it is on its own. (Or maybe you could make it always require another key to select, just to be sure.) Under the current system, it makes sense to have top priority for exploders only.
Assigning skills while paused: I don't think this should unpause the game. Keeping it paused would allow much greater control. Cycling through highlighted lemmings should be done without unpausing too (I can't remember if L3 let you do this or not).