Location History is something different I believe. It's whether Android / Google stores the history of places you've been too. It says nothing about whether it's doing things with your current location.

On Android 7.x:

Settings -> Location -> Recent location requests, tap each service, tap 'Permissions' and revoke the permissions for each app that has it.

Settings -> Location -> Location services, tap each service and disable everything.

That seems to fix it for me. Of course, at some random time in the future, Google will enable them again. I'm fairly certain I disabled this a few times already.