Familiar key signing over video call
So your protocol goes like this:


Alice generates a key pair $(a_{priv}, a_{pub})$ and sends $a_{pub}$ to Bob.
Bob generates a key pair $(b_{priv}, b_{pub})$ and sends $b_{pub}$ to Alice.
Alice generates a message $m$ and sends $Enc(Sign(m, a_{priv}), b_{pub})$ (or $Sign(Enc(m, b_{pub}), a_{priv})$, I'm not sure which of both is usually used by PGP) to Bob.
Bob decrypts and checks the signature to get a message $m'$.
By a video call both verify that $m' = m$.


Your key verification scheme is based on two ideas:


If Bob did succeed to decrypt some message encrypted by Alice using $b_{pub}$, then Bob must be in possession of the corresponding private key $b_{priv}$.
If Alice knows the content of a signed message which could be verified using $a_{pub}$, then Alice must have been the signer and be in possession of $a_{priv}$.


But this doesn't work in presence of a man-in-the-middle attack for the previous key exchange and the exchanged message.

Assume Eve is able to intercept all messages between Alice and Bob.

Then the attack goes this:


A → E: $a_{pub}$
Eve generates a new key pair $(a'_{priv}, a'_{pub})$.
E → B: $a'_{pub}$
B → E: $b_{pub}$
Eve generates a new key pair $(b'_{priv}, b'_{pub})$.
E → A: $b'_{pub}$
A → E: $Enc(Sign(m, a_{priv}), b'_{pub})$ 
Eve decrypts the message, strips the signature and re-signs and re-encrypts.
E → B: $Enc(Sign(m, a'_{priv}), b_{pub})$
Bob checks signature and decrypts, and gets the same $m$ as sent by Alice.
Video call verification shows that "everything is okay".


If the message also contains parts of the key to be used, that would have to be changed by Eve as well, of course.

So no, you can't get around checking the actual finger print of the keys (or something derived from it).