That's great, but what about when someone doesn't have access to a physical router
Geralmente, todo o tráfego da Internet atravessa vários ISPs e roteadores de nível de operadora, e nenhum deles costuma ser fisicamente acessível pelos usuários.
Seu quarto parágrafo é um pouco incerto. Acho que você não entende como o NAT funciona.
A razão pela qual o encaminhamento de porta é necessário é devido ao NAT. O NAT oculta vários sistemas atrás de 1 endereço IP. Você só pode falar com esse endereço IP publicamente visível. Se você deseja obter algo por trás deste IP, você deve passar por este IP. Você não tem escolha. Sem o encaminhamento de porta, o roteador habilitado para NAT não sabe qual máquina por trás dele enviará tráfego de entrada não solicitado e assumirá que você está tentando falar com o próprio roteador.
Se você está falando sobre um programa que aceita solicitações em nome de um cliente por trás dele, o nome para isso é "proxy" e você certamente pode fazer isso. Um roteador é um lugar lógico, mas não necessariamente melhor, para que seja executado e acessível. Existem proxies para muitos protocolos, HTTP, SIP, etc.
When the first one receives the request to form an actual connection, it accepts
Isso nunca aconteceria. O "primeiro" está por trás de um roteador NAT, o roteador NAT recebe a solicitação primeiro, e não qualquer pessoa atrás do roteador.
O IPv6 corrige isso fornecendo um espaço de endereçamento grande o suficiente para que o NAT não seja necessário para preservar os endereços.
Não há protocolo especial envolvido no NAT, é tudo TCP / IP.
O que é diferente de um roteador padrão não-NAT é que, do lado de fora, os nós só vêem e sabem sobre o único IP público. Tanto quanto eles sabem de um nível TCP / IP, há apenas um sistema nesse IP enviando muitas solicitações. Se nada como o Javascript, um proxy ou outro tráfego no nível do aplicativo estiver deletando no IP privado de alguém, o exterior não poderá saber o IP privado.
O recurso NAT deve acompanhar quem iniciou quais conexões (somente atrás) para que ele possa encaminhar o tráfego de entrada destinado a si próprio para o host apropriado. (Isso é possível porque cada conexão de saída possui uma porta de origem aleatória exclusiva, portanto, pode simplesmente mapear as portas de origem para os endereços de destino da LAN).
Eu acho que houve um programa que tentou trabalhar da maneira que você está dizendo, enviando um roteador NAT um pacote TCP fora de seqüência (a seqüência é SYN, ACK, SYN-ACK) que pode enganá-lo. Eu também ouvi falar de roteadores NAT que erroneamente permitem conexões TCP de entrada em portas que o tráfego UDP é enviado.
Mas uma boa implementação de NAT vai verificar suas tabelas internas para conexões mapeadas, e soltar o pacote se ele não corresponder a nada visto de dentro. Você não pode contar com falhas de implementação para fornecer uma solução confiável da maneira que você está pedindo.