Most of the things greene suggested are hardy perennials that will survive winters that cold, with a good generous layer of mulch or dead leaves. Coleus are easy to overwinter, just by taking cuttings into the house, and rooting them on a window sill for starters next spring. That's about the most colorful thing you can grow in deep shade.
Hardy periwinkle is a beautiful groundcover, blooms with nice blue or white flowers in spring, and also comes in a variegated form that is really nice. Spring flowering bulbs like tulips and daffodils are another nice thing in a shady area. The flowers last much longer in shade than in sun. You'd need to plant those in the fall, though. They make a wonderful combination with the periwinkle, coming up through the foliage in spring, then when they are finished the periwinkle grows up to hide the maturing foliage.
As Deb suggested above, Lily of the Valley is also wonderful in the shade, has nice foliage and the flowers smell heavenly. They only bloom for a short time though.
But Daylily, Bearded Iris and Salvia won't bloom well, if at all, in deep shade. You could plant them near the edges of the really shady area though, where they will get sun in the morning or afternoon. Anywhere your marigolds bloom, those would do well also. (yes, marigolds do seed themselves).
