Granting restricted permission roles
As you mentioned, User protect should work well. Combine this with Role Delegation to restrict what roles they can assign.

Might also be worth keeping an eye on the Administer Users by Role module, although there is no D7 port yet (in progress here).

Let me know how it turns out as I'm going to be solving this issue on the site I'm working on soon.