With me, music does far much more in establishing feel/appropriateness than lyrics do (tonal qualities suggesting a certain color palette and certain kinds of shots; see http://www.animemusicvideos.org/legacy/ ... hp?v=10286
), but from what I know about Fozzy and what I can see happening in the lyrics, I'd suggest Perfect Blue. It's got a lot of the same psychological 'issues' as Eva has, and it also benefits from not being done to absolute death (sorry, Firestorm, but there are already 847 videos out there using Eva/EoE to some degree).
I like kthulu's Noir idea as well, but it looks to be tough to do this song without using a lot from the end of the series. When it comes down to it, though, it's your vid; watch some anime or AMVs (shorter and free) and set up the source that you think works best.