Even if both parents have brown eyes, they can still carry the gene for blue eyes, so their children can have blue eyes if they happen to inherit the blue-eye gene from both parents. Cheddar man's ancestors presumably carried the blue-eye gene, whatever their eye colour was (which we don't know). Blue eyes and dark skin are not unusual in North Africa, but I don't know whether or not that was the case many thousands of years ago.
The report on Cheddar man says that he would not have been able to digest milk as an adult, so he probably didn't eat cheese. That doesn't mean he didn't drink cider, though.