Glancing at Reddit I see comments like "this is a statist solution". I guess a few people don't appreciate the irony of inverting an infrastructure of government control, to build strong anonymous peer to peer networks.
There's no irony in handing control of those systems to government. In a fantasy world these passport certificates aren't subvertable - they'll always be issued honestly, never duplicated, and the private keys in them will stay in them - but in the real world that's not something you can guarantee. People are worried that we'd find out in a few years for Snowden Jr. that the (three-letter-acronym) had been making up fake passports for the purpose of running Tor nodes - certainly possible - or had been issuing passports that they actually had the secret keys to after all and were signing anonymous signatures using that fancy crypto-math to run said Tor nodes.
Or hell, if this is one-passport-one-tor-node I'm sure these large surveillance/police/military government bodies could just ask their employees to donate their passports briefly to a good cause...
Anyway, two out of three of your examples have better solutions to them; notably there's no need to trust nodes to be "honest" anyway.
My approach to the solution would be to have a completely open hardware solution for TPM modules with design, manufacturing, and distribution overseen by a coalition including the likes of the EFF. These would take the place of government issued passports, and would fit the bill of being relatively cheap, but not so cheap as to allow trivial mass accumulation.
To further gain confidence in the node distribution, employ methods like Kaminisky's 'nOOter' and Eli Ben-Sasson's 'PCPs' as presented at the SJ 2013 conference.
Something really interesting re: TPM is it appears you can make open-source community audited remote-attestation-capable hardware. The trick is that you can build hardware that creates the secret keys after manufacturing in some kind of initialization process, yet have the process itself verify the integrity of the "strong-box" the computer is in, and have the hardware implementing that process be designed such that third-parties can take it apart and verify that the hardware would have done that honestly. Pulling off this trick requires a minimal bootstrap routine in ROM that creates the keys on startup - since it's ROM you can pull the circuit itself apart to verify that the ROM was guaranteed to be executed and thus the keys generated securely when the internal batteries were connected the first time.
As for the "strong-box" to provide the tamper resistance, tempered glass and mirror silver work well. The glass is notoriously difficult to breach without causing it to shatter due to the internal stresses, and mirror silver lets you make tamper-detection circuits that detect that shattering and wipe the internal keys. Both techniques are low-technology, yet effective.
Now to verify the remote attestation, you take production lots of these boxes, have third-parties select sample boxes and tear them apart looking for flaws. The chance of getting away with shipping a bugged box is some function of how many sample devices were audited, the size of the production lot, and how good you are at detecting bugged devices. A secondary audit technique is to put Bitcoin private keys in the devicse, pay coins to them, and see if any get spent!
I spent some time a few months ago going through some of the details and think I covered them in principle, but just didn't have the time to pursue the project. There's a lot of details to cover, most of them nitty-gritty hardware level stuff, and you're likely to end up with "reasonable" assurance rather than anything all that convincing. But for Tor routers that's not a bad start. Combine it with Mikes passports maybe for more assurance.
