I largely agree with you on these points, but I still think that it's more likely expressed post-intelligence, rather than something that was behind the wheel before man came about physiologically.
There is still a lot of randomness, like you claim. Plus, there are lots of genes that become dormant because they aren't needed- the gene for expressing something changes, so a trait no longer arises, but it might be as simple as another mutation that changes the chemical balance a little that brings the trait back.
This is broaching into speculation, and talking about it makes me very interested in the potential of testing genetic expression in this sense, but facial features are sort of compounded. It's not just a handfull of genes that can change the shape, color, consistency, etc. of the face, but hundreds of genes. However, with none of them being selected for, you'll end up with an average mesh.
Take height of a plant. There are many genetic factors, but if there's not any reason for it to grow any higher, because of no competition, then it will all average out. The next generation, even if the genes are 'randomized', will be roughly the same. It could be that way with facial structure too, largely.
Which would mean that humans, with intelligence and the necessity to discern faces, would have then a driving factor towards selecting for certain facial features. Over many generations, this compounds and creates many different diverse, refined looks.
It's the exact same mechanism for as to why other changes would happen- a small population, for whatever intelligent reason gains a certain trait that leads to more breeding- facial structure. Which trait is selected for might be random, which would be why it branches off in the first place.