1) Les quelques visiteurs que nous étions pourraient patienter quelques heures. le sujet est : les quelques visiteurs
3) Un de ces hommes originaires d’Afrique regarda l’un des visiteurs qui montaient l’escalier.
– Qui est-ce qui montaient ? les visiteurs (ils montent tous mais un seul est distingué).
– Si vous gardez « originaires » au pluriel, cela signifie que tous les hommes sont originaires d’Afrique ; le singulier impliquerait que seul « un de ces hommes » est originaire d’Afrique. C’est au rédacteur de le décider. 
Pour le 2) à vous de décider, en tant que rédacteur –  s’il s’agit d’une addition ou d’une exclusion : que vous lez-vous dire en fait ?
4)  On peut envisager les deux : soit un cumul pour le pluriel, soit on laisse au singulier en pensant « tout » et « n’importe quoi » expriment la même idée.

Pour la phrase 3 on peut écrire  :
3) Un de ces hommes originaires d’Afrique regarda l’un des visiteurs qui montaient l’escalier.
– Qui est-ce qui montaient ? les visiteurs (ils montent tous mais un seul est distingué).

Mais on peut aussi écrire (voir la ponctuation)
3) Un de ces hommes originaires d’Afrique regarda l’un des visiteurs, qui montait l’escalier.
– Qui est-ce qui montait ? un seul parmi tous les visiteurs
Et :
3) Un de ces hommes, originaire d’Afrique, regarda l’un des visiteurs qui montaient/montait l’escalier.

Pour la phrase 2, il semble très très probable que  le président soit un exemple d’homme d’influence : il faut donc le singulier.

Pour la phrase 4 :
Dans votre message du 8 mars 2016, Joëlle vous répondez ainsi à la même question : l’imprécision de « tout » et de « n’importe quoi » rend le choix difficile : de quelle réalité s’agit-il ? Après réflexion, il semble qu’il s’agisse en fait de la même imprécision (tout et n’importe quoi signifient pour moi : ce que je ne peux pas préciser) , donc c’est une réalité englobante qui est homogène par son imprécision. Donc je laisserais le singulier.
tout et n’importe quoi + verbe | Question Orthographe Voltaire
Une réponse que je trouve fort pertinente.

1- ……que nous etions pourraient
2_
3-…….hommes originaires ………..l un des visiteurs qui montait
4-la première phrase est correcte

Je vous remercie pour ces éclaircissements.

Merci pour cet approfondissement, Tara.