I can tell you about a project I did which was a lot of fun. I was somewhere between 11 and 13, with my Apple II. That should tell you when it was, since it came with only Integer Basic (no floating points) which didn't get fixed until I added a 16KB Language Card for Pascal and Floating Point Basic (Applesoft).
Anyway my Dad had this amazing collection of National Geographic magazines, you know with the yellow spines, going back for years. It was in a cabinet in the basement and we would often go down and search the several keywords which were on the spine of each one of the magazines. We'd be talking about something and suddenly my father would say, let's check out the National Geographic, or maybe it was let's see what the Encyclopedia says. I do remember reading a couple sets of encyclopedias but Geographic was great because of all the maps inside.
Well maybe the best of all was a year end compilation of the World Book encyclopedia set we had, because one edition had a fantastic description of Smalltalk and how you could control an actor on a stage (well that's Director and Lingo now.. maybe another good avenue for you to check). Images of this incredible personal, programmable environment danced in my head for years. I dreamed it existed inside an infinite digital watch, etc. I think my dreams were better than those space invaders watches they came out with. Anyway, next best is probably the map of the Moon in Geographic. Point is, these things stick with you. I took two classes at a high school on Saturdays, fortran with punch cards (it was fun but horrible since we had no idea what we were programming or how) and astronomy (which was plain great, this high school had a mini planetarium!). Now, I program and I'm into astronomy.
Anyway I got this idea to build a system to organize them and in the end you could input the keywords, date, and article names in each issue and run a search. This was in Basic but it would be similar in Perl. The interface was a plain text terminal display, maybe ANSI and curses would be good.
I also remember once doing a school art project that consisted of an animated drive through a vector graphic drawn desert, you drove with a game paddle. These were ideas I came up with after learning some of the basic things that were possible.
Anyway to go on about the Geographic system, I think if you have a similar collection at home and use it similarly this would be great since your child likes reading. Or maybe if you have dinner time discussions that turn educational like we did, you could assign something to look up (all us kids would get picked on one night or another to run up the stairs and come back with the right encyclopedia entry for example).
You need to keep it very simple, relevant, and hopefully rich in the sense that you can keep using the same system to work out different things to try in the future (if she is still exploring and not bored with it). So you might just start with hard coding the names of some tv shows and printing them out. Then you could sort them. Then maybe what time they start, and then you could print everything on Friday Night, and so on.
If there is an analogue now, maybe the first place to start is learning how to draw colored bars on the screen in vertical or horizontal orientations using commands like "color=xxx" and "line a,b to c,d". You can draw pictures together easily and if you have thick bars (maybe they are one character thick) you can fill the screen with impressive designs in no time. This was a lesson that sunk in. If you are on a budget or want to keep everything in the same programming environment so the tools are always at hand, you might even create Perl packages for your daughter, I'm thinking of something that uses Readline and maybe curses to provide a prompt and mimic some of that great Apple visual feedback from minimal inputs. Maybe you would separate the prompt from the plugins, and provide another plugin which draws each letter she types as big as the screen. Maybe you could have it print a page for each letter. This kind of thing is easy for kids to understand and is fun, but an explanation of how it works is always possible too.
One possibility that is quite easy is for you to get an Apple II simulator like Catakig. I love it not just for nostalgia but because it has less clutter and more meat. You can also get software for free, one I recommend is Infocom's Zork, a text adventure (like unix adventure) but with a very good natural language parser. "Go North" and "Examine Lamp" are the kinds of commands that would get her used to a keyboard, creating her own imagery based on detailed descriptions, and getting her used to navigation in virtual spaces.
The other thing is, Perl is wonderful but there are lots of interesting things out there for kids to learn programming. I tried Logo but didn't like it. To clarify that since there is a related comment above, Logo is great for some things but once you get the basics, I at least felt constricted by a sandbox, which is exactly where you are. You don't get dirty. The Apple and Basic was just right for me since I could do graphics, mess with the modem, even mess up the monitor's frequency by blitting values to the framebuffer from 6502 assembly code. So while I do know Perl will grow with your child for a long time, I'm not sure she will be able to do visually exciting things unless you help her.
I think you might want to supplement your Perl lessons with use of other visual programming methods (if there are any which aren't actually harder to use than Perl). I'm thinking of my 150 in 1 electronics set, which was a blast even though I got stumped by most of the poorly documented schematics in its manual. I still wish I had had more help with electronics at that age, I just remember being stuck with the schematics and then a heavy tome on logic and gates.
Maybe a visual music synthesis environment would be good. I'm thinking of MAX which lets you wire components together on a screen and actually control external devices or generate tones. It is professional but I think kids appreciate that. However it can get pretty technical so you will have to answer a ton of questions. The neat thing about both MAX and Perl is that you could purchase things to attach to your computer so that your child can control physical things with it, for example lights, speakers, cameras, and so on. One friend I know is a digital artist who used MAX, Perl, and the web to wire up a seismograph in California with an exhibit space in Tokyo.. and with MAX the data sent over the net drove all kinds of great bass rumbles on a 5 speaker system in a cave-like environment. You could lie down on the floor over the bass speaker and feel the rumble intensify as the Earth released the stress in tons of rock. I'm sure that sort of experience, and understanding how it all works and being able to tweak it, is wonderful for giving creativity free reign and learning concepts with all the senses. At least I know I would have been pretty impressed as a 9 year old!
One last idea is Sim City. I have always remembered a trip to the Toronto Science Museum where they had a few color displays built into podiums with touch screens that showed a fire fighting simulation. You could start fires, dig trenches, spread foam from helicopters, and so on over a map of a forested area. It was very fast, interactive, and had great sound effects. It was similar to the exhibits in the Franklin Institute I saw once too, which had a button for almost every exhibit which you could use to make things move. A simulation gives you a good tactile feeling of dynamics, and all of the three systems above are transparent and to some degree conducive to hacking. There is a little known title called Sim Tunes by a friend named Toshio Iwai. There is a demo here. This and other related titles (he has done one for the playstation) let you compose your own music in a wild animated environment in which you draw your composition.
If you can keep things simple and let your daughter think up her own ideas while shielding her from the daze we sometimes get from information absorption overload, you both will have a lot of fun and she will have a great head start in whatever field her interests end up taking the two of you.