Many years ago, I TA'ed a class that did exactly that, teaching Scheme to gifted students ages 12 to 15. The text we used was "The Schemer's Guide" by Iain Fer

Many years ago, I TA'ed a class that did exactly that, teaching Scheme to gifted students ages 12 to 15. The text we used was "The Schemer's Guide" by Iain Ferguson, supplemented with a large helping of locally-prepared material about propositional logic, recursion, Turing machines, etc. In that way, Scheme comes across as a natural implementation of these concepts. It's worth noting that 90+% of the work in this class, including programming projects, was conducted as pen-and-paper exercises, not on a computer.