Ssh – Multiple users, Multiple servers, SSH key management

Here is the situation.

I have 5000 servers broken into "groups" of 100.
Each "group" has 1 SSH key pair, that will allow access to any of the servers in the group.
I have 60 users(some human, some not) that need to access all 5000 servers. The users are all on different computers, some PC (putty) some Linux(ssh).

manually:
Adding a new server to a "group" seems to be simple.
Adding/updating a user would be a nightmare.
Adding/updating a new group would be a nightmare.
Syncing group keys to user stations would be a nightmare.

ssh-agent/pageant works for a single user, on a single workstation, but doesn't seem to be scalable.

Is there software that can handle this management? Some kind of proxy perhaps? Or automated server based key retrieval protocol?

EDIT

I appreciate the help so far, however I think I am not being clear or not understanding the suggestions.

Some more information: Each of the servers is a remote system with no access to the Internet and the connection speed is generally slow. Each server has only one entry in its authorized_keys file. I do not want or need individual user keys. I just want many different people to use the same key for each group.
Right now we are using password authentication, and keep a list of a passwords for each group on a piece of paper. This works for our team. But it will not work if we switch to key based authentication.

Do the suggestions still make sense? If so, can you please be more specific as to implementation details.