I stumbled on this and as I once did something similar decided to post an answer.
I did the following:
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.
In my case I had an HTTP server running on my device. So I just sent HTTP HEAD request for essentially nothing on port 80. If device responded and Server header is properly named, then this is my device.
But I couldn't go fast without pinging first. HTTP is TCP and request is big, so timeouts have to be 4 seconds for WiFi. Doing this for 253 addresses is slow as hell. But you wouldn't have 253 devices (probably) more less HTTP servers. (or in your case, phones)
Considering router logs is very good idea, and easy. And even faster than pinging all. Some routers do not even need logging in for getting to them.
Also, it is worth checking whether your device has UPNP support. If it does, you can use UPNP to detect its presence. This would be official solution (listening on broadcast for UDPs of UPNP). But all devices does not support it. But all devices do not support ICMP also. (they don't wish to be bombarded needlessly).
There is another interesting possibility. You can fish for DHCP packets and see when a router is giving a new device an IP address. But this wouldn't work for devices with static IPs. They wouldn't even touch the network until they need something. Connecting to WiFi itself is on another layer and cannot be easily detected unless you wish to act as a sniffer. I am not sure even if it is doable with network adapter in a promisquous mode. I think additional hardware would be needed for this.
To achieve ping in Python, without subprocessing to ping program and losing speed, you have to create raw socket and construct ICMP packet manually. It is not hard. There is example of it somewhere on the web. Of course, to send it you will need root permissions as does the ping. This is a drawback. If you will distribute the software you cannot expect users to want to run it as root.