I too was trying to change my safari icon and after reading all of the suggestions here, nothing worked but after several trial and error attempts, I figured it out.
First, open the "Get Info" window for Safari. Second, double click the icon or picture you want to make the new Safari icon (I'm not sure if it has to be a png file or icns file but I used an icns file). Once the file is open and it opens in preview, hide the sidebar and select the entire picture. Copy the selected picture and go into the Safari "Get Info" window, click on the Safari compass in the upper left corner and paste.
The picture in the "Get Info" window should change automatically and on the spot, however the dock icon and the icon in the applications folder wont change. Restart your computer and everything changes.