I really dislike trying to make stage and character selection a skillful process. It is inherently outside of the game, and therefore will only unfairly benefit those who are better at picking stages/characters.
I don't see how stage and character choice are "outside the game." Choosing a stage and choosing a character are necessary to play. It's definitely part of the game. Maybe it's not part of the gameplay vis-à-vis character interaction, but it's certainly part of the game. Further, anything you turn into a "skillful process" will benefit those who are better at said skillful process. This doesn't mean there is anything wrong with it.
You should tread carefully with the word "unfair." There's really nothing unfair about a player having more tools in his toolbox being able to force his opponent into more bad scenarios. The same happens with the player vs. player interaction you defend so vehemently. For the most part, something is only "unfair" if it is not available to both players. Things like port priority, for example, are unfair. But it simply being the case that a more knowledgeable player performs better is certainly not unfair. In fact, even something as absurd as a player having more Star Wars knowledge causing him to perform better is not unfair. It may not be what you want to test (which is, of course, just a matter of preference), but it's not unfair.
Things get iffy really quick when you start basing advantages off of elements outside of the game itself. For instance, I don't think someone should benefit simply because they play two characters that complement each other when it comes to stage bans. For instance, I have a Marth secondary, which means if I am playing a set vs. a spacie and they cp FD, I can just switch and put them in a tough position they couldn't possibly have anticipated. That's just a quick example of why I would highly recommend picking characters before stages.
I don't agree with this at all. It just reeks of scrubby mindset. You should anticipate potential problems with any counterpick. If I counterpick Rainbow Cruise as Marth, expecting my opponent to go Peach, and he goes Fox instead, this is a mistake on my end, or a good decision on my opponent's. We shouldn't be catering to players who aren't smart enough to plan for adverse scenarios.
With regards to this specific example: surely your opponent should have known better than to go to Final Destination if he were not prepared to handle a Marth there? There's always the possibility that your opponent will use another character.
There's a lot of things like this in the current rule set. There's a lot of little traps and tricks you can use in the stage selection process to cover your *** on bad stages with secondaries or cover bad matchups by picking a stage they're okay with and then flipping the script by changing characters. As a PLAYER, obviously I use these to my advantage as much as possible. As a TOURNAMENT ORGANIZER, this is a glaring weakness of the rule set.
There's no reason to call this a weakness of the ruleset. You can dislike it, I guess, but I don't see anything you've brought up as problematic.
The stage/character selection process should be as up front as possible so that when it comes down to the match neither player is surprised by anything. It's really just unfair, and chaotic to the point that it feels random ("oh, you have a secondary and I couldn't have accounted for that with my ban/stage selection, cool...").
There's nothing wrong with your opponent having a trick up his sleeve. The logic you're using to deem this a weakness of the ruleset could similarly be applied to any lack of knowledge on the part of the player. And, again, be careful with the word "unfair."
Also, there isn't really any way to account for the "problems" you've brought up. There may be some contrived solution that is unique to a particular game, but, seeing as we're discussing rulesets in general, and not how to artificially balance Melee in particular, it seems like you're just choosing a different, equally arbitrary methodology for how to start matches. Choosing your characters first won't somehow prevent the same problems in general.