No friends,
I can understand Nagzz's situation.
You tell very easily to ask the employer for a certificate and to deposit the salary in the bank. But the person who interviews Nagzz probably doesn't know and is an ignorant fool. He is adamant about the payslip even when Nagzz has explained that he is being paid in cash. There are circumstances where many work without proper payslips and deductions, but that does not mean they should be asked for a payslip. The interviewer should be sensible enough to judge whether the candidate is telling the truth rather than depending on a piece of paper.
Nagzz, these ignorant fools don't understand why people like you and many others are paid in cash without any written records. I don't hesitate to call them ignorant fools.
They should focus on your education and skills rather than being interested in your payslips. It's better to bluntly reply to these interviewers right in their face.
Many people are there who will consider your education and skills and pay you a good eligible amount with a payslip and all, but for all those, we need to wait, which I am also doing now.