Sewing with felt is nice for beginners, too, because it doesn't ravel and you can sew it wrong sides together. I think there are probably a lot of tutorials free online for little felt projects, too.
If you don't want to do felt, I think little drawstring bags are easy and would be useful for a little boy.
My daughter is 5, and she's pretty good at embroidering designs drawn on fabric. She can do a little hand piecing, as long as I draw the line for her to sew on.