Design for Multiple Users Per Role

I want to start working on an implementation for the Node Permissions that have been talked about. While I have no idea just yet how I'll do it all, I have an idea of how the project can be divided into manageable "parts". Node Permissions, as it is, will probably result in a lot of refactoring in the Drupal core (and I'm not familiar enough with the system to be the sole designer).

I've been randomly thinking, and I've broken down the idea into smaller, hopefully more-manageable parts that can be integrated on an incremental basis.

1. Users can belong to Multiple Roles. I started this and then gave up when I realised I didn't know what I was doing, but I'll probably start it up again. A new database table (something like "users_in_roles" needs to be added that maps the uid to an rid. (Right now, the user table maps directly to the role table.) All of the SQL will need to be changed, of course. My primary problem with this, as of now, is Serialization in the user.module. I don't know what it does. I have a feeling that it might have to do with authentication in the Drupal Network - if that's the case, then adding Multiple Roles might break cross-compatibility.
2. Adding a moderator to roles. Assuming that people like the idea of appointing a moderator to look after a user role, this would be one next 'feature' step.
3. Adding permissions per taxonomy We can adapt the node system to start checking permissions baesd on the taxonomy permissions. Not sure what needs to be done here, though.
4. Adding the set of "standardized" permissions. The Permission Requirements thread mentions a few schemes for standardized permissions, and I think this is a great idea - it'll cut down on the "maintain book" vs. "edit book" vs. "administer book" kind of permissions we see right now. This will also probably break every
   module.
5. Customized User Groups. This should be done in tandem with per-node permissions, since one without the other isn't very useful.
6. Per-node Permissions. When taxonomy permissions are set, then per-node permissions shouldn't be a big deal.

I'm really just brainstorming at this point and I haven't looked too much in detail for many of the above issues (especially permissions). However, if we plan to implement this well, I am very confident that database renormalization must occur (therefore breaking a lot of SQL) and the Module APIs for permissions will change (therefore requiring a lot of module rewrites). As a result I plan to start looking at the code in detail so that, if we do make major changes, there'll be plenty of time before Drupal 4.5.0 is released to look at the design issues.

Yeah, so as I said, I'm sort of thinking out loud here, but if anyone has any insights please share them.

So that reminds me - what kind of necessary steps are needed to propose changes to the core Database tables?