Does anyone have any idea how to retrieve deleted records data from Apex data loader or otherwise from Salesforce except from the Web service?
You can't. The only way to get deleted records through the API is to use queryAll, and DataLoader doesn't use queryAll ever.
(Sorry for the resurrection here.)