When my granddaughter was 4, I let her sit on my lap and pull the pins out as I sewed. I don't always use pins, but I used them so she could have something to do. She loved watching the machine work and pulling the pins. It isn't sewing, but it was to her. Her attention span was short, and afterwards she loved playing with my magnetic pin holder and pins. I also let her help pick out fabric.

For anyone who wants to start their little ones off VERY young, when they show an interest, there is always plastic canvas and in the yard section you can find large plastic, non-pointy needles that are used to sew granny squares together. Give them some yard and a piece of plastic canvas or even the stuff you can make rugs out of, sorry, I don't know the name of that. They can practice, practice, practice....