I think I have come up with an idea that should be secure but would like to hear an expert's opinion on it:
First step: use a protocol between the two parties A and B to come up with a random number R that none of the parties can force to be a given value.
Second step: calculate a secure hash of R concatenated with the self-signed certificate and use a prefix of the result with the desired length, e.g. the first 10 characters as the string that has to be shown and compared.
The first step could be implemented as follows:
A and B each use a secure RNG to come up with 256 random bits, rA and rB. Then each party calculates the the SHA-256 of that value, let's call those H(rA) and H(rB).
A connects to B over the TLS link and saves the certificate that is used. All subsequent connections to B only succeed if the cert stays the same (pinning).
A sends H(rA) to B and B replies with H(rB).
A sends rA to B and B replies with rB.
A and B both verify that the other party's value and hash match. Abort with warning if mismatch.
Both parties calculate R = H(rA | rB).