I think I'm going to steal your bit about failure being a lesson.
Another hack I've applied in the way I talk with my kids is to sometimes say things that are obviously wrong. Starting with very obvious errors and as they grow older moving to more subtle lies about the way things work. If they don't catch the error I continue reasoning along the same line far enough into absurdity for them to get that I'm wrong. It makes them aware of questioning what people say and to think through themselves what is reasonable and what is not. And they now are very proud and happy whenever they are able to point out when I'm wrong about things.
I also never, ever proxy them towards other adults. If we are eating at a café and they want a napkin or buy another pancake they have to talk to the staff themselves. When they want ice cream I give them money and they have to buy it themselves. Because it is such an asset to be comfortable talking to people and getting what you want. It makes them believe in their own abilities.
The way I teach them is in two ways: Whenever they show me something they have written or drawn I point out the spots where they have corrected mistakes i.e. by striking a word and say "Wow, look how much you learned!". And whenever they hurt themselves or mess up something bad enough to complain or cry about it, while I comfort them I ask "So, what did you learn?".
I've done this consciously for several years now and it is interesting to see that it is actually affecting how they think.