Как обычно устанавливаются двусторонние соединение в интернет?
Вы очень вовремя. Я собирался ложиться спать после прочтения учебника Cisco. Начнем с того что маршрутизаторы при работе с NAT меняют в кадре на уровне протокола TCP ip адрес отправителя и порт отправителя на случайный порт, который записывается в специальные таблицы. Когда приложение отвечает на запрос пользователя, оно фактически также посылает пакет на IP адрес указанный в заголовках транспортного уровня. То есть по сути, когда клиент послал запрос, работа через клиентский NAT-порт еще может вестись некоторое время.
Кстати вообще все это называется двухстороннее квитирование с использованием флагов и т.д.
Почитайте про модель OSI и в частности TCP/IP, создание сеансов и т.д.
Надеюсь помог чем смог.
Насчет веб-серврера и сервиса, то что вы говорите тут желательно сервис, хотя под apache есть web-сокеты и расширение под php позволяющее как раз делать это.
Клиент периодически соединяется с сервером и проверяет, есть ли для него что-нибудь новое и интересное. В общем случае иначе нельзя. 

В частном случае можно пробросить порт через NAT и коннектиться к клиенту как к серверу.