The way I could do it was by using the docker api. I used the docker-py package to access it.
The api exposes a labels dictionary for each container, and the keys com.docker.compose.container-number, com.docker.compose.project and com.docker.compose.service did what was needed to build the hostname.
The code below is a simplified for code I am now using. You can find my advanced code with caching and fancy stuff that at Github at luckydonald/pbft/dockerus.ServiceInfos (backup at gist.github.com).