I can confirm that finding companions with unassigned points is possible.
I got 3 companions with a lot of unassigned attribute&skill points;
I did lots of tests. I literally spent my last 2 days to figure out what the factors are when it comes to make companions spawn. One of my tests was hiring a companion from a city(it was Diathma) and taking that companion to an another city by kicking from my clan. When I went back to Diathma after 1 day(in game time), a new companion was there. And this new companion had lots of unassigned points. After doing it, I tried it again on an another city and it worked again.I was successful literally twice in a row. But then, I tried it like 10 more times on other cities and didn't even work once. So I believe even though what I did was a factor, there are other factors that affect when&where&which new companions spawn.
One thing I'm sure about is, after new companions spawn, there is a limited time for getting them with unassigned points. That's why I'm checking every nearby city's tavern while I do other things on the map.