Honestly, I think you should create a secondary list called ListNameHistory. Index your SharePoint columns in the new list now to help with large list size. I would create an extra column called MainListID or something so then you can pass the list item ID to the history to tie them together.
Then within your workflow I would just use the create list item action to track your history and just make sure you write the List ID to the MainListID column and then whatever data you want to store in the list. You can copy/paste the action every time you want to do something for history and you could even add a notes field you could pass information too to also help track changes.
Also, by creating a secondary list, you can manage this list easier and get full list functionally when you need to do something with the data.
As far as Tasks Lists go, you shouldn't have to worry about that getting purged every 60 days because that is just a regular list so you can retain that data for as long as you would like.