Otras alternativas de protocolo? El más estandarizado es el http.
Realmente por poder, puedes inventárte tu el protocolo. Depende para que sea.

Que estén o no en la misma red no te debe preocupar lo más mínimo.

En Java es un poco más complicado trabajar con sockets bajo nivel. En python puedes usar la implementación de sockets en C y haces la aplicación en muy poco código y con más control.

Si buscas algo ya hecho, chequea apache. Tienen un cliente http que siempre me lo encuentro cuando busco movidas de sockets en java para android y proyectos open source.