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.