Far as I'm aware all those we're added to the game via Heaven's Ward patches. I know I have most (if not all) those haircuts and I didn't do anything to unlock them. Try using the barber at an Inn, that's how I found them.