Eu tropecei nisso e como fiz uma vez, algo semelhante decidiu postar uma resposta.
Eu fiz o seguinte:
1. Ping all addresses within given network and subnet (excluding network and broadcast addresses)
2. Wait for response has a timeout so that if device doesn't answer from furthest corner of your WiFi it is considered not present.
3. So we get all IPs on the net that answer to ICMP packets.
4. Then use each detected IP to ask for more and decide which device you like and which one you don't.
No meu caso, eu tinha um servidor HTTP em execução no meu dispositivo. Por isso, enviei apenas uma solicitação HTTP HEAD para praticamente nada na porta 80. Se o dispositivo respondeu e o cabeçalho do servidor está corretamente nomeado, este é o meu dispositivo.
Mas eu não pude ir rápido sem primeiro pingar. O HTTP é TCP e a solicitação é grande, portanto, os tempos limite precisam ser de 4 segundos para o Wi-Fi. Fazendo isso por 253 endereços é lento como o inferno. Mas você não teria 253 dispositivos (provavelmente) menos servidores HTTP. (ou no seu caso, telefones)
Considerar os registros do roteador é uma boa ideia e fácil. E ainda mais rápido do que pingar tudo. Alguns roteadores nem precisam se conectar para acessá-los.
Além disso, vale a pena verificar se o seu dispositivo tem suporte para UPNP. Em caso afirmativo, você pode usar o UPNP para detectar sua presença. Esta seria a solução oficial (escutando na transmissão para UDPs do UPNP). Mas todos os dispositivos não suportam isso. Mas todos os dispositivos também não suportam o ICMP. (eles não querem ser bombardeados desnecessariamente).
Existe outra possibilidade interessante. Você pode pescar pacotes DHCP e ver quando um roteador está dando um novo endereço IP a um novo dispositivo. Mas isso não funcionaria para dispositivos com IPs estáticos. Eles nem sequer tocariam na rede até precisarem de alguma coisa. Conectar-se ao WiFi em si é em outra camada e não pode ser facilmente detectado, a menos que você deseje agir como um sniffer. Não tenho certeza, mesmo que seja possível com o adaptador de rede em um modo promisquous. Acho que hardware adicional seria necessário para isso.
Para conseguir ping em Python, sem subprocessar o programa ping e perder velocidade, você precisa criar um socket bruto e construir o pacote ICMP manualmente. Não é difícil. Há um exemplo disso em algum lugar na web. Claro, para enviá-lo, você precisará de permissões de root, assim como o ping. Isso é uma desvantagem. Se você distribuir o software, não poderá esperar que os usuários o executem como root.