The Little Schemer 
 - https://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0...
The Tandy/Radio Shack books for the Color Computer series (and it's astoundingly good LOGO implementation) were amazingly clear and concisely written with lots of examples, and because in those days even a disk drive wasn't a guarantee, all the examples were written to be hand-typed and experimented with.
There were even books in those days that aimed to teach kids machine language! 
That said, I think Djikstra and Felleisen may be slightly right about the long-term usefulness of old-fashioned BASIC and LOGO for learning, but there are a few books in modern languages that come close.
Hello World! was explicitly written to hearken back to those old manuals, by a father aiming to teach his 12-yo son programming with Python.
Land of Lisp and Realm of Racket also call to mind those old books as well, though they're targeting a bit older audience and have their quirks (LoL is a bit in-love with huge nested trees and a-lists in the examples, and Realm of Racket tends to gloss over a lot of the examples and expects you to just read the sample code rather than walking you through the process completely).
The Little Schemer is also a fantastic little book that takes on the form almost of a set of brain-teasers, and teaches recursive thinking entirely by example and in methodical detail. The later chapters can be a bit stumpy, but if you go through the book step by step in regular sessions it builds on itself pretty well.
All of these are aiming at around the 12+ age range though, I don't think there's much out there anymore for anything younger.
Here's how it works. Say we have a recursive function like map:
map f  =  -- We'll ignore the base case since there's no recursion here
map f (x:xs) = f x : map f xs -- This is the interesting part
How? Well, let's abstract over the recursive call, replacing it with a function that we'll add as parameter to our definition:
map' _ f  =  -- Still boring
map' g f (x:xs) = f x : g g f xs -- Pay attention for later!
All we've done so far is replaced map' where it should be on the right-hand side of its own definition with g, and then added g as parameter of the function. We end up with a double g on the right-hand side because of that added parameter.
OK, now what? Well, we need somehow to make g be map', the thing we're defining. which means we need somehow to pass our definition of map' to itself, so that (in the second case) we'd end up with something that evaluates to:
map' map' f (x:xs) = f x : map' map' f xs
So how do we make this happen? Well, what is map map f (x:xs)? It's map applied to itself, then to some other arguments we need. So the key, it seems, is to figure out how to apply map to itself. Well, in the lambda calculus that's pretty easy :
why f x y = f f x y
lambda f. lambda x. lambda y. (f f) x) y
map = why map'
map f (x:xs) = why map' f (x:xs)
== (by def. of `why`)
map' map' f (x:xs)
== (by def. of `map'`
f x : map' map' f xs
Voilà. So that wasn't too hard. It's basically two steps: (1) abstract over the recursive call, then (2) figure out how to pass the function you're defining to itself. If you look at the Y combinator, you'll see that that's exactly what's going on there.
If this didn't make a lot of sense to you, it's probably because I wrote it on my iPad at 4:30 in the morning. It really is just those two steps: abstract over the recursive call, then self-apply. ...
To get deeper into the recursive mindset (if you're not there yet) and to build up deliberately to the Y combinator, take a look at one of my favorite books on functional programming, The Little Schemer . (And watch out for the jelly stains!)
0. And it's ill typed, but never mind that. It's not possible to define the Y combinator (or any other fixed-point combinator) in the simply typed-lambda calculus, so just imagine that my Haskell-style syntax is untyped, like the basic lambda calculus.
1. Although, again, there's no way to give fix a good type in the simply typed lambda calculus.
The book The Little Schemer is a great way to learn to think recursively. It has been 5 years since I read it, and I haven't kept the skill fresh, so I've probably lost most of it.
Later, I moved on to the Clojure books. Working through the Little Schemer was invaluable (and its bibliography is excellent too).
I'm a total noob with this stuff but I've been really happy with Clojure (and more recently ClojureScript/Om) :)
"Maybe I would be confident in my skills to apply to some tech jobs. Or do some freelance work"
Don't expect to get "normal" tech jobs by the time you're good enough unless you can disguise your age, age discrimination is fierce in this field. But as noted by you and many others, there are many options.
I'd also add that at some point unless you've forgotten all your math and don't want to refresh it try Structure and Interpretation of Computer Programs (SICP) (http://en.wikipedia.org/wiki/Structure_and_Interpretation_of..., http://ocw.mit.edu/courses/electrical-engineering-and-comput...), everything you need is free and online. If it's a good enough fit for you it will teach you some foundational things that'll make you a better all around programmer and system designer. E.g. one way or another learn big O notation (https://en.wikipedia.org/wiki/Big_O_notation) and its significance.
Essentials of Programming Languages
The Little Schemer
The Little Schemer <http://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/02...; and
Clause and Effect <http://www.amazon.com/Clause-Effect-Programming-Working-Prog....
Also a help is that the languages they use ('use' is a more appropriate word here than 'teach') — Scheme and Prolog, respectively — are much more mathematical in nature than typical mainstream languages are.
It's an excellent introduction to thinking recursively. The others in the series (The Seasoned Schemer, The Reasoned Schemer) are worth reading too.
It takes you more step-by-step than SICP and once you get more practice with those books, SICP will be much more paletable.
Get dozens of book recommendations delivered straight to your inbox every Thursday.