The problem to solve is how two humans make the initial exchange of credentials required to establish a relationship between their respective freedombox installations.
The proposed solution
One possible way to do this is to enable two users, Jane and Ken, to exchange some information (GPG fingerprints of their keys, optionally other data like a vcard) scanning a QRcode when they meet in person with their mobile devices. In a decentralized network with cryptographic protection, each person's key should represent themself -- not their name, not their driver's license, not their address, not their passport. They can be "Uncle Charlie" in one person's freedombox, and "Charles Knox, Esq." in another's. In a third freedombox, the key could represent "Guy I met at fish dinner with JoAnn, March 2011". Or "Chuck who I always see in the library on Tuesdays".
The implication for FreedomBox design is that a user's key should be transmitted WITHOUT further identifying information. Any identifiers for a received key should be provided by the receiving party.
The updated status of key verification can be then transmitted back from the phone to their respective FreedomBox, securing future communication between Jane and Ken.
A use case
Since it's not advisable to keep a key that can sign other keys on the phone, one use case that emerged from various discussions on irc and in real life is the following:
Jane and Ken run the same app with screen showing a QR code the PGP key ID+fingerprint. Optionally the QR Code can also contain other information, like a full vcard. They get their phones close, activate their camera and, in turn, scan the other's QR code. After the scan, the app shows the data in a human-readable format for confirmation: if confirmed, the data goes into the addressbook for further editing. Once Jane goes home and connects the phone to the FreedomBox in a secure manner (private network? cable?), the FreedomBox software greets Jane with a message asking her if she wants to sign Ken's PGP key. If she confirms it, the key is retrieved from a keyserver and signed with Jane's secret key, the new signature is sent to Ken.
Using bluetooth or some other form of wireless communication doesn't guarantee protection from snooping or spoofing, QRcode does not have this problem. QRCode also has other advantages: it works if the phones are offline, can be printed on business cards (not both parties need to have a phone), it forces users to be mindful (scan, see the data on your screen; instead of 'push a button, something magic happens on the radio waves').
Development has started. Follow the development of ManusVexo on gitorious.
Other useful resources
There is an OpenPGP implementation for Android called Android Privacy Guard (APG). The project is integrated with the K-9 email client and seems already usable. Among AGP planned features are some of the things that FreedomBox is tackling: key server support, implement some trust model, allowing easy key signing, preferably across devices and link contacts and public keys.
QR codes cannot handle a full OpenPGP key and all its certificates since it only handle 2953 bytes of 8-bit binary data.
Monkeysign of the Monkeysphere project currently displays a qrcode representing your PGP fingerprint and it also tries to read the other's fingerprint. The piece that manages the key signature protocol is missing. Monkeysign assumes internet access as it downloads the key, so the web of trust should just propagate through that. Monkeysign's git repository git://git.monkeysphere.info/monkeysign holds the python code. It can probably be used to cover the key verification use case for laptops and other GNU/Linux based mobile devices (Meego comes to mind).
Update: Monkeysign has been refactored to be able to sign keys, thanks to a new general purpose Python GPG API.