They key part is "Warning: Once you have pushed a commit to GitHub, you should consider any data it contains to be compromised. If you committed a password, change it! If you committed a key, generate a new one."
Removing the secrets from the repository is nice to have, but not that necessary - what is mandatory is to ensure that the compromised secrets are no longer useful, since they aren't secret any more and won't be ever again.
I am rather disappointed in github for publishing this guide. The portion at the top stating
> Warning: Once you have pushed a commit to GitHub, you should consider any data it contains to be compromised. If you committed a password, change it! If you committed a key, generate a new one.
Is a good argument as to why you shouldn't let users erase this data from history, it's already out there so no matter how painful or convoluted your process is for regenerating auth credentials is, you need to do it if you've published them into your SCM. If the process is painful you might want to simplify it because you'll probably need to do it sometime in the future again... yes even you large corporate workers who have no control over credential regeneration, an arduous process leads to credential sharing between projects which is another horrible thing.
