What do you think I should have (within reasonable margins) before I approach a publisher?
Well, you've got the first part: being able to present a well-rounded, rich and (relatively) original, professional idea. What isn't evident from your case so far is have you thought your ideas out further into some level of detail? Is this a sport? Why the mask? The football isn't just a football. Why? Who were those robots? Why do they exist? Expect to be challenged such that each answer is used by the panel to generate another drill down question. Now, at some point, you don't know; that's fine. Publishers don't want a weak vision.
You should preferably have an interactive prototype (a.k.a. demo), but barring the inability to find a bunch of devs to make it happen, you realistically could approach a publisher with your video (and presumably other assets) and a good GDD, with emphasis on the differentiators of your game against others, but not as an expose on technological prowess.
Apart from that, be prepared to step through the user experience. Who's your target market? (No, it's not "the consumer".) What are your own ideas for attracting players? What are ideas for retaining them? For getting them to recommend it to friends? The publisher can help, but a publisher wants to see your own thought-process more than anything else.
Also, remember publishers are investors, not gamers, so you'll need to be able to make a case for how the numbers will look. How much art? What will it cost? How much code? What will it cost? What's the administrative overhead? What's the timeline on the spend? Where are the dips in funding that have to be covered? Divide your game into broad functionality pieces and be able to talk budget-wise about each of them. The answer to "How much money do you need?" is not "As much as you can give me." Likewise, think ahead about some of the common "contract terms" like exclusivity or right to sequel on the IP.
When you say studio, you mean game developers?
Yes. But, it's probably the trickiest of the three possible avenues. Also, there's a potential conflict between the studio's art teams and the fact that you'll be setting the art direction.
I'm considering your advice on trying to raise a demo in parallel to other studio work. I know many studios who want to jump to the next level of game development do this.
Note that self-publishing is getting better and better. Usually, the best things you get out of a publisher is access to funding, a deep marketing network and "creative" feedback (usually centered around what sells, although big studios are getting more and more "looking inward"). Since you seem to potentially have experience in the first two, and creative feedback is likely not an issue given your milieu, you should strongly consider self-publishing.
However, you should not expect the success of Modern Warfare 2... But, it may be more rewarding and fun (in a keep-you-awake-at-night-kinda-challenge way).