Well, I recently wrote something similar for RMVX. It was an addon for another script but the part relating to what you are thinking of is contained almost entirely in this post:
http://rmrk.net/index.php/topic,39569.msg464112.html#msg464112There is a lot there that is RMVX specific, but the basic idea I had was to create a wrapper class for the basic array and use that to hold the basic data. However, for each additional level of a skill, I added another with the index of the original skill + 1000. So if the Fire skill had the ID 102, then level 2 of it had the ID 1102, level 3 2102, etc...
Those additional skills were held in a hash and merely accessible via the $data_skills global variable.
As that means all skill levels have a unique ID and are accessible via the regular $data_skills, all that was left to do to distinguish between actors was add that unique ID to the array when they learned the new level of the skill and remove the old one (if it was a replacement system). That said, that solution is pretty well as heavy as it gets on memory usage, but it seemed to me to be a fairly good way to do it.