My BF hasn't been able to find relief from dandruff despite out paleo lifestyle, even during a whole 30 his condition didnt improve. He was also shampoo free for the past 6 months. As somewhat of a last ditch attempt, he tried a couple of drops of tea tree oil massaged into his scalp after his rinsed his hair (about once ever two days). And, would you believe it, it worked! I'm not all down on the science behind it, but I believe tea tree oil has anti-fungal properties and dandruff can be caused by a fungal overgrowth. It took him about a week to be flake free, and he is such a happy chappy I thought I would post in case anyone else is in a similar situation.
You can find out a bit more on my tumblr blog Perth Paleo

Let me know if it works for you!