You can grant read  access to everyone at the list level  and then organize your
document by folder (department). Right click on a folder and select manage
permissions. Here you will want to break inheritance. Leave the group there with
read access  that you assigned at the list level and add the new group that you
want to allow to edit  docs and give  them contribute  permissions.

On a side note, you can also create a view that hides the folders so that users
don't even know they are using a folder hierarchy if you want to. You just have
to be careful that docs get loaded to the right location. We've implemented
event handlers for a few clients so that they are able to select the Department
from a dropdown in the metadata, and then the event handler moves the document
to the appropriate folder. Lots of options...