Get a reputable auditor to vouch for you, by giving them access to your infrastructure for a while. Of course it’s not foolproof (you could change everything the minute he leaves) but it’s the best you can do. Bonus points for making it a yearly event.
I work for an ISP and have toyed with the idea of offering a "private, no logs" VPN service. As someone running such a service, what would it take to convince you that I wasn't logging information that could be used to identify you?
(Obviously, there would be logs of some stuff -- just not the kind of things that would allow you to be individually or personally identified.)