Como o seu ISP fornece apenas endereços IP privados, você provavelmente não poderá aceitar solicitações de conexão de entrada na sua rede, que não façam parte de uma conexão estabelecida originada na sua rede.
I'm wondering if there's a way to work around this problem without having to need a public IP. Since, after all, two users on Yahoo Messenger or Facebook Chat are able to find one another and exchange data despite both sides being within the internal networks of their respective ISPs.
Os clientes de serviços como este realmente começam fazendo uma conexão de saída para um servidor conhecido operado pelo proprietário desse serviço. As solicitações de saída, obviamente, não são bloqueadas pelo NAT, apenas solicitações recebidas. O servidor central provavelmente encaminha mensagens entre os clientes também.
Uma VPN resolveria esse problema. Se você deseja executar sua própria VPN, precisará de um sistema em algum lugar que tenha um IP público real. Se você quiser acessar isso usando dispositivos iOS, provavelmente desejará verificar a configuração de uma VPN de estilo PPTP ( poptop no Linux suporta isso). Você também pode procurar um provedor de VPN de terceiros (o Hamachi pode funcionar, nunca tentei).