How to get students engaged in more basic topics in programming?

Create games that apply some basic concepts. You'll need a progressive set of games. Start out by setting up your game board (homemade is fine) and your paraphernalia. Your student will prick up his ears right away. Explain the basic concepts needed to play the first game. The game should be exciting but quick.

Each set of paraphernalia should have a number of variant games that can be played with that set.

Suppose a game involves converting a decimal number to Base 2. You don't need to explain in detail, prior to playing the game, WHY computer scientists are interested in Base 2.

Many games will involve rolling one or more dice and then doing something that requires applying some technique.

Example: each player will, on his turn, roll five 0-1 dice (each side shows either a zero or a one). These five digits define a five-digit binary number. Write down the number you've rolled. Now figure out what that number is in Base 10. Say the answer is 12. Move your guy 12 spaces on the game board. Set up your game board like a simplified Chutes and Ladders, to make it exciting.

Edit #1: Responding to the new version of the question. It is tempting to want to give students the background information needed before giving them a hands-on project, because from a teacher's point of view, that is the most efficient way for the learning to take place; but sometimes it's useful to throw something at the students and let them flounder a little. Then you'll have their attention when you explain why something didn't work, and what's really going on behind the scenes. Have you ever tried that?

Edit #2: You could ask the students to program a simple game, and then have them try out their neighbor's program.