I think you may be able to make use of the stateChange event. One of the possible event types is VideoState.CONNECTION_ERROR and another is VideoState.DISCONNECTED which may also work.
Try giving that a shot.
If those don't work, the only way I can think of would be to either do a HEAD or GET request for the flv before you attempt to load it. Only a successful response would trigger the video loading through the normal method. I don't remember whether Flash supports HEAD requests, but if it does that would certainly be the better option.
If Flash does not support HEAD requests then you may be better off having a simple, server-side script that could verify the existence of the flv before you actually request if. That way you can use a simple GET request without having to retrieve the whole file.
INLINE THINKING
I am just thinking, another possible solution using GET would be to cancel the load as soon as bytesLoaded > 1K (for example), or something like that. As long as you are checking for a size greater than the 404 response you are getting, you should be able to assume the flv is being loaded.