I think the secret is to break down the distinction between computer operation and computer programming. If they're interested in computers and the stuff you can do with them a gentle way to get started programming is to find and use whatever scripting language whatever programs they already use have to automate stuff and make random creative hacks, rather than starting from "hello, world" and learning the fundamentals first.
For example:
Have them screw with the interface of their favorite websites: pick a greasemonkey script that already does anything on that site and change it to do something different.
Learn the macro/scripting interface of whatever productivity software they have some reason to use already and make it do something.
Find a game they like that has an active scripting or modding community, and fiddle with the game rules.
The idea is to make the mental leap that writing software is just another way of getting the computer to do what you want, and that there's one big continuum from poking buttons in a dialog box to amateur hour hacking to writing "proper" software. Eventually you'll have the ambition to do something that requires more than just plugging pieces together and making edits to stuff other people wrote, and that's when you'll be self-motivated to obtain the knowledge that will make you a more effective programmer.
I realize this is at a way more primitive level than most people think of as learning to program, but IMHO the CS 101 stuff where you learn a language and how to make simple programs from scratch is closer to the "middle" than the "beginning".