It means one time (at least) in a set of times or a period of time (a while).
A while is an indefinite period of time. If the condition holds at even one moment during that period then the condition holds for once in a while.
Update (as suggested by @Cerberos) from comments I wrote here:
"Where is it said that once means 'at least one time'?"
"Once" means one time. I added "(at least)" gratuitously. Consider it removed, if you like. The phrase "Once in a while" means one time in an arbitrary (indefinite, nonspecific) time period. As such, it has come to mean repeatedly one such time in one such arbitrary period, that is, multiple arbitrary occurrences in multiple arbitrary time periods. Since the periods are arbitrary, it means, in effect, at least one time in an arbitrary period. If it occurs once in time period A and once in time period B then it occurs twice in the union of A and B, which is another arbitrary time period.
"yours is a comment rather than a real answer."
Fair enough. But you seem to think that "once in a while" is an idiom, and you wonder about how the idiom evolved. My answer is that a literal reading of once in an arbitrary while suffices. No real evolution ("come to mean") or "idiomatic usage" needed as a hypothesis. Same thing with "once upon a time", although we don't use "upon" here nowadays, so that is idiomatic now.
"I don't think the meaning is actually literal as Drew suggests. It should mean "one time in a period of time" not "from time to time"."
Actually, I did not suggest that the meaning can only be literal, i.e., that a literal meaning is necessary. I said that a literal meaning suffices - it can be read literally, and the meaning in that case is what one would expect. And a reading of "from time to time" follows from a literal meaning of "one time in a period of time" (because...because...time).
I tried to show how the meaning you understand is related logically to a literal meaning. That relation is as much of an "evolution" as I can come up with, I'm afraid. It doesn't pretend to be a real, historical evolution but is a logical becoming (relation between concepts). Then again, history can sometimes be underpinned by logic... ;-)