To answer my own question, I don't think 2) is possible, due to the legitimacy of constructs like:
Here is some ''italics with a [[link|that switches ''off]] the italics.
That's a problem we're going to come across a lot. Most parsers solve it by requiring the syntax to be well-formed. Since wikitext is meant to be a foolproof as possible, we don't want to make that requirement, which means we have to write a parser that can understand a terrible mess of tokens.
I think toggles is the only way to do it, although even then it's hard since the result isn't going to be a tree.
The only alternative I can think of is running the wikitext through a tidier first that detects that kind of mess and adds the appropriate close and reopen tags. It requires an extra pass through the text, but might be unavoidable. Basically, we accept that wikitext can't be described by EBNF, so start by parsing the wikitext into a more restrictive form of wikitext which can be described by EBNF, and then parsing that. It's a mess, but it's probably better than what we have at the moment.