Hi Marina
There are lots of API's, many of which could probably delete some of the data for you, although this would have to be done in the right order.
You could also consider doing a mass of roll-backs on all the payroll processes, although this would start to get arduous as time rolls on.
There are other options which may be preferable to your client...
1. You may wish to consider obfuscating personal details to make them less identifiable? Things like NI number (or your Legislation equivilent), employee number, name etc. There are some 3rd party companies which sell software which can scramble the data, or you could hire a consultant to do it for you (hint hint).
2. How about creating a training database? Use a 'gold' master configuration environment with all the associated setup date (orgs, jobs, positions etc) and then generate sample employee / assignment data in it. This can then provide a development instance for your developers to play in?
3. Finally, you could get your developers to sign non-disclosure agreements and get them vetted/security cleared etc and simply trust them loose on a production copy.
Here at NHS we have tried all variations. The obfuscation/scrambing of the data did not work too well as we originally used these environments for support work too, and by scrambling the data it made it difficult to correctly identify issues with people!
We now have 2 systems in place.
For pure development work, we have a cloned instance containing the config and set-up, which some then use and create their own test data in. I built a set of processes to generate random data - creates employees, assignments (with multiple date-tracked changes), addresses and self-service users etc.
For support and system test work, we use cloned copies of the production system, and then control access to certain accounts only. People requiring access need to sign non-disclosures etc.
I guess your solution would depend on how much effort the client is willing to invest (time and money), against how much trust they place in their developers. We're not all hackers

Regards
Baz