In my current job the Cozyroc componets are used and I can recommend them. It´s a supported way to write data into the CRM entities. However, to make a backup you don't need to write data, instead you just need to read data.
To solve your issues:
1. How do I obtain a list of all entities -- Use the data dictionary (i.e. InformationSchema System Views)
2. How do I obtain a list of all fields within each entity -- Use the data dictionary (i.e. InformationSchema System Views)
3. How can I download - lets say 500 records at a time. -- Use the Cozyroc library, make your own component extension. The problem hier is how to make a kind of batch/bulk request to the web service. The Cozyroc "Dynamic CRM Source" has an option called "BatchSize" (Specify the number of rows to be retrieved as a batch. The maximum is 500.) Here
is the link to the documentation. I think you could try it for free.
If not you could always extend a component, but you have to put in a balance the development cost and time in order to accomplish such a task.