Other Random Possibilities

Instant Messaging
Server and Client exchange commands / packets / etc over IM protocols.
Easy to do.
Already leaks through most firewalls.
Perl modules exist.

Sessions over any other protocol
FTP
Send data with 'ls' filenames.
Recv data from 'ls' output.
NNTP
Send data with list-message query.
Recv data in message.
Etc, etc, etc