I've had bad skin most of my teen and adult life (I'm 34 at present). Eating a paleo diet helped in a few minor ways, as well as some "paleo-ish" lifestyle changes like getting more sunlight, swimming in salt water, etc...
My body acne (never on the face, but neck, behind ears, my back, and thighs) did not clear up with a paleo diet or even fasting, IF, Calorie Restriction, etc, nor did the dandruff on my scalp and bearded face. Finally, I did some experimentation with using vinegar (apple cider to be exact) as a shampoo and face wash replacement.
Within a week my dandruff was gone. Using a washcloth in the shower doused with vinegar to scrub the areas where I had body acne eventually cleared that up as well.
If it starts to come back, I just repeat the treatment again.
Now, this would insinuate that my own issues are purely bacterial - not that I'm insinuating that for yourself, however I will say I'm relatively clean (for a male meathead weightlifter-type), so initially I was a little put-off by the fact that this was all bacterial... but everyone has tons of skin bacteria, and it's highly likely that persons like you or I simply have stronger immune responses to those bacteria.
In short, I don't think fasting, or CR is your answer to address bad skin. I don't even think that diet solely will be your answer (although it will help considerably). There are things outside the sphere of paleo that can help you.