it depends on if you want all 4 users to access all 3500 records.
If thats ok i would advise creating a group containing all 4 users then assigning the group against the 3500 records.
Then setting the OWNER to the group name (be careful with this, as if you create a group name to "TEST" then the actual group name is not TEST, it will have some numeric values before it) But if you use this method let me know and i can tell how to find out the actual field value.
If you need to assign 875 records to each user then i would be just the matter of creting filters to split it by Company name (for example), and then using global replace to update a field to state that record is owner to that user.
You could use the OWNER field, and then set the STATUS to "I1" - this way any other user (apart from admin) would not be able to edit the record.
HTH