This Rostra doc says that the VSS signal is at:
Passenger Floor-96 pin conn @ ECM
Pos. 93 Loc3 35 pin conn @ ECM Pos24
for a 99-04 Subaru Impreza.
Since they don't give diagrams in that doc, it's hard to tell how they do their positioning. Their other one, for '86-'95 vehicles, shows pictures of the connectors, so it's easier to find where it is.
What I would do is, try the other wires behind the speedometer. Since you're not cutting into any wires, it shouldn't be too hard. Also, I don't think you're necessarily looking for a 0-5V signal (I think it could also be 0-12?), just one that changes with speed.
Otherwise, I would go for the ECU option. Start with what the rostra data has, you'll probably find that green/yellow wire there.