Yes, sending the key in the first (plaintext) email would work.
This is essentially what most people do when they blindly accept a new ssh host key.
Even if you are not going to verify the other side identity -like you should-, before sending mildly confidential data, the bets are still good for you:
- Perhaps you are not being spied every time. Your email could pass through.
- If at one point you start being spied, past exchanges would be safe.
- They might not have the program available/enabled to MITM all your key exchanges.
- They don't know if you are going to immediately phone your recipient to confirm the fingerprint.
- Two-way messages need to be altered for an indefinite time.
- You could verify your partner identity weeks/months later.
- There is a limited timeframe to MITM your exchange (compare with reading an email archive).
Unlike a passive reading of your messages (such as accessing the mailbox of the target), performing a MITM on a key exchange is noisy (and likely more illegal), and will put the victim in paranoia mode if discovered. Thus, unless you are a high profile target, I don't think it would be sensible to fiddle at that level (you may be considered more important than expected, though and there are stupid attackers, too).
So yes, exchanging your keys via unencrypted email is a workable solution. But do your part and try to verify them.
Beware: if dealing with non-technical people, many technical people and generally, expect lots of “how to use this?” basic questions, people mailing you their private key with the public one, etc.
If you are going to exchange only PGP mails, you could automatically filter as spam everything not signed/encrypted to your key. (Spam issue)
As the email existence is intended to be secret, you could use a random email address such as <fingerprint>@domain (only one piece to transmit, instead of email + fingerprint). On the plus side, this forces your correspondent to get the fingerprint right if they are going to start the communication. On the con side, homograph attacks are easier.
I guess this system is indeed used by privacy-conscious [government] people. Publishing keys/fingerprints in https pages is also common.
As much as the X.509 system can be more suitable for such organization, I don't think they will be using them. There's also the duplicity if they are using OpenPGP for other correspondents. And of course, a secret agent in a covert mission wouldn't be using a X.509 key -nor email address- identifying him as such. ;)
gpg --search nsa.gov for some funny keys published in the keyservers.