Things to consider
My first strategy was to wait until I've received a message from all neighbors and take the min before broadcasting, but this results in only the first layer around the leader (distance=1) receiving the message as they will not have received a message from the nodes with true distance of 2.
I am assuming that the length of each edge between neighbours is one. Have each node maintain a route to the leader, not necessarily shortest (initially null). Have each node send the route and a list of all of its neighbours to those neigbours as soon as it has a viable route to the leader.
Initially the neighbours of the leader will send out their route (one hop). This will cause nodes two hops away to compute a route and send it out. After N steps nodes N away from the leader will have at least a route to it, not necessarily shortest.
As soon as a node has a route to the leader, it sends that route together with a list of its neighbours to the next hop node on that route, which will retransmit it, with its list of neighbours, being sent according to the route itself, so we know that differences of opinion on routes can't cause messages to be sent indefinitely round cycles.
The leader knows its neighbours, so it knows when all of its neighbours have sent it this information, and generally it has enough information to know when it has reports from all of the nodes in the graph. It can then pool the neighbour lists from all of the shortest route reports to work out the correct shortest route from each node to the leader, and send messages bearing this to each node in the graph.
At each point in time the leader has a set of nodes from which it has received information (route to leader and list of neighbours) and a set of nodes which it knows exists (its own neighbours and neighbours mentioned by other nodes in messages it receives). When the set of nodes from which it has received information is the same as the set of nodes that the leader knows exists it has all the information it needs. If there were any other nodes out there not known to the leader consider a route from such a node to the leader. As you travel to the leader you will eventually meet a node known to the leader or the leader itself. Consider the first such node. Either the leader knows its neighbours, in which case the leader knows that an unknown node exists and it does not have its list of neighbours yet, or the leader knows the node exists but does not know its neighbours. In either case the set of nodes known to the leader is greater than the set of nodes for which the leader has neighbour lists, so the leader knows not to stop collecting messages yet.