I had another talk with someone more familiar with debian. In this talk we came up with following approach. If you like this better, I can submit a patch for this.
Approach: First look into /usr/share/pam-configs for any config including pam_tally. If something is found, disable it with pam-auth-update. Also emit a message to the user, that pam_tally is deprecated and the user should switch to pam_faillock. At this point the system should be in a good state, if the user did not manually configure something in /etc/pam.d. Just to be sure, we do an additional check for pam_tally in all files in /etc/pam.d. If this comes up negative we can assume everything is ok and continue the installation. If it finds an occurence of pam_tally, we generate a pam config without pam_tally and use ucf to let the user choose how merge our changes. Additionally we emit an error message about really making sure the pam config is in order.
