The browser cache wouldn't be an issue. The sensible approach would be to generate the HTML with a different file name referenced in the "link" tag for the icon. Even if the files are cached on the user's system, "fire.ico", is still different from, "gate.ico", and the browser will deal with it accordingly. The only way it would conflict is if you dynamically modified the contents of the same icon file every time a page was loaded, and if you did that, it'd be a crap-shoot anyway. Two users could access pages on the site simultaneously, and they'd both download a file with the Water Rune in it, even if the guy whose script ran first by a millisecond drew Lightning. And that's assuming all the file locks didn't crash the scripts.
Now if the designer's plan is to just stick, "favicon.ico", in the site root as a default, and be done with it, then it's impossible.
The thing is, an icon is usually meant to be representative of the site or brand, and it's kept consistent as part of a site's identity. There are exceptions of course. For instance, if this site chose instead to have a stylish, "S" (assume the Suikoden title font is immediately recognizable), it might be useful to have just the "S" on general pages, and to smash it up with a number when you're on a page for, say, Suikoden 3. Just randomly changing the site's icon isn't really in line with the feature's purpose. If it wasn't just a 16x16 image, doing so could be said to add something to the site's appearance, but being so tiny, I really don't think it would.