This will only work with higher icon resolutions, so when finding an icon online try to go for at least 128x128. You should have no trouble finding icons for popular sites.
Of couse, you can also use this to substitute default icons for custom ones.
If it does not work, you will need to create a "dummy" bookmark to work on; use the instructions below.
Assuming you want to do this for mail.goole.com , you are going to add a bookmark for 9gag.com (it could be any website, this is just an example)
You are going to proceed as if you wanted to change the icon for 9gag.com and then just edit the name and URL of the bookmark in Safari when finished.
The program will shut down Safari by itself, so you don't need to restart.
When you open it again, you should have the desired icons.