Applying a function/workflow that triggers on Create/Edit to older records!

Applying a function/workflow that triggers on Create/Edit to older records!

So at work, we've recently put into place a new system where various functions/workflows are used to dictate a number of statuses regarding our client. 

Right now, this is all working fine for any newly created Client records in the 'Clients' module.

The problem is that retrofitting this into older records is proving difficult. What I tried is making a dummy checkbox called 'Mass Update', and applying a mass update on that to trigger the workflow on all the older records, but it says that workflow rules will not trigger if more than 1000 records are updated at a time. The alternative I thought of was just applying the mass update 100 records at a time, but this would take hours.

I'm curious if there are more elegant solutions to this, because surely someone must have grappled with a problem like this in the past!