I recently discovered, after trying to change Safari's icon, that Apple's apps in Snow Leopard have read-only permissions enabled for all users except root:wheel. This eliminates users' ability to use copy-paste replacement icons in the Get Info panel.
As a workaround I quit the Finder, and relaunched it as root in Terminal:
sudo /System/Library/CoreServices/Finder.app/Contents/MacOS/Finder
I was then able to paste a replacement icon into Safari's Get Info panel. Then, after relaunching the Dock, my icon appeared.
[robg adds: You can quit the Finder using Activity Monitor and it won't restart. If you try this hint, remember to again quit the Finder and relaunch it as your normal user once you're done. I haven't tested this one, so I can't say if it breaks code signing or not.]

