At some point, you've got to trust somebody.

Or, else, just don't connect to the internet at all.

Is there any way to prove that some service like that is actually trustworthy?

This is the right question to ask and the ultimate reason why I don't use a commercial VPN service. Ultimately a commercial VPN is just moving the trust from the Internet service provider to the VPN provider (or in Tor's case to the exit node provider)

Personally I just block all ads across everything, select more privacy friendly software, avoid known privacy invading services where feasible and otherwise generally just enjoy not knowing the scope of adtracking because I never see the ads anyways!