Как сконнектить два приложения без общего сервера?
Если речь идет о взаимодействии в рамках одной сети WiFi - то нет проблем. Используйте широковещательные пакеты для уведомления других устройств, что в сети есть устройство, готовое работать по вашему протоколу.
Если это более общая задача, не привязанная к одной сети и WiFi, то даже если устройства будут знать адреса друг друга (не важно каким способом), могут возникнуть проблемы с доступом к устройству из-за оператора связи, т.к. в сотовых сетях обычно используется NAT оператора, который препятствует прямому доступу из интернета к устройству (NAT как правило включен в любом WiFi роутере и т.п.). В этом случае придется использовать какой-либо сервер в интернете со статическим адресом. 
Существуют варианты обхода NAT, но они так же требуют сервера для инициализации соединения, а затем уже устройства могут работать напрямую. Подобные техники используются, например, в VoIP. Гуглите по протоколу STUN.
можно.
смотри p2p-сети, их вагон и маленькая тележка есть, на все вкусы и варианты понапридумовано.
желательно чтобы хотя бы одно устройство в линке должно быть с белым ип(ипв6), иначе колхозить варианты обхода nat.