"When you install the app they steal your contact list and populate their database that way."

What if you avoid using the system default contacts store, i.e., keep it empty, and instead you use an app like OpenContacts.^1 To apps like TruCaller, it will appear the the user has no contacts.

1. https://f-droid.org/packages/opencontacts.open.com.openconta...

https://github.com/sultanhamer/opencontacts