Changing the license of every article would take a long time, but it could be done. Changing a fraction of the articles would be even easier.
The fraction that have only been edited by logged in and currently active users, yes.
And that's even if you accept your assertion that "Changing license would require the permission of every contributor that hasn't had all their contributions removed".
Do you question the assertion? The only way you could get away with not having someone's permission would be fair use, but that causes problems with reusing parts of articles. While one sentence may be fair use when used in the entire article, it might not be fair use when used as part of just that paragraph.
Finally, anonymous contributors don't really have standing to challenge most of the problematic parts of the GFDL. They're anonymous, so they can't sue you for not putting their name on the title page or in the section entitled history.
I really have no idea how the GFDL interacts with anon users. As far as I know, the license doesn't mention them. That's one of the biggest problems with the GFDL for a wiki.