$ cd ~/Library/Safari
$ rm WebpageIcons.db
$ ln -s /dev/null WebpageIcons.db
The first command sets the proper working directory, the second removes the current favicon database, and the third recreates the database file, but links it to /dev/null, so that any output written to the file is summarily discarded.
[robg adds: This works as described, though I personally prefer to keep the favicons. Note that this hint replaces this one, which only works for older versions of Safari.]

