I have given exactly that some thoughts and I do think it is doable. Most problems arise from possible attacks on the distributed directory system (if you don't want to use something like DynDNS).
At one point, there must be "trust" established. That could work by means of "benevolent dictators" signing user keys with the "dictator key". Dicatator key signing would have to be hidden behind an anonymizer/mixnet, or the dictator might be bribed or forced into attacks on the directory system.
if you don't have the "dictator root certificate", you can't have any form of authentic directory data.
Regarding directory topology - you basically need to automagically create a hierarchical tree of directory nodes. Each node must elevate itself to directory node based on a probability related to the total number of nodes. Determining the totoal number isn't easy in the face of attacks either. One solution could be that "node generation" includes Proof-Of-Work
(http://en.wikipedia.org/wiki/Proof-of-work_system). That would makie it harder to generate a large number of bogus nodes and fool legit nodes into reducing their inclination to become a directory node.
Note that "adaptively" deciding to become or not to become a directory node is a Bad Idea, as the attacker could create tons of directory nodes and after some time start to deliver wrong results to directory queries.
The secure voice transmission process is actually very simple and could be done based on SSL/TLS, ssh or GNUpg. Man-in-the-middle would be defeated by calculating gibberish sentences from the public key checksum and both parties would read that gibberish over the voice channel to the other party. We assume you can't synthesize voice without the other party realizing the attack, of course.
Over typical DSL lines you don't need any codec, either. (but there are several FOSS codecs around)
What both TOR and Skype provide is a directory system and if you want to replicate that, it is going to be some hard work. If you can live with DynDNS or even transmitting the IP address over "government phone", the technology issues are quite simple.