A frase mais correcta é: «Tivemos a possibilidade de nos aproximar.»¹ A  frase em questão é composta por uma oração principal — «Tivemos a possibilidade (de)» — e por uma oração subordinada completiva — «nos aproximar». Saliente-se que o verbo da oração principal («tivemos») se comporta como verbo leve², formando com o seu complemento directo («a possibilidade») um predicado complexo («ter a possibilidade»). Esta construção admite apenas orações subordinadas completivas de infinitivo preposicionadas («de nos aproximar»). Além disso, tais orações infinitivas (ou não finitas) mostram preferência pelo infinitivo impessoal, visto o respectivo sujeito ter a mesma referência que o da subordinante, ou seja, «nós».

Sempre ao seu dispor.

¹ Não se pode dizer que «Tivemos a possibilidade de nos aproximarmos» constitua uma clara agramaticalidade, por causa do comportamento particular dos infinitivos a que se associam pronomes reflexos. Ver resposta Concordância em orações de infinitivo, novamente.

² Sobre verbo leve, ver resposta Fazer enquanto verbo-suporte.