To go along with your combination of Lemmings and Lost Vikings, why not call it Lost Lemmings (gotta love the aliteration)?
I would like it if the icon pickups were still in there, but when one character picks them up, the icon goes to the character that can use it. That would open up a lot of ideas for level design and puzzles where one guy (like the scout) has to go somewhere to pick up the skills for the other guys to pass an obstacle. Also, if you decide to add abilities that aren't strictly from Lemmings, then consider other puzzle elements and derive the abilities from them. A few examples are moveable blocks (pushing and pulling abilities), waterfalls (walking with umbrella, maybe used by anyone?), metal blocks (magnet to move closer, even through walls to land on switches), and poles or hooks (to latch onto with a rope or grapple).
For C++ tutorials, I like
www.cprogramming.com and some other one that I can't find right now...
But the current build of this game isn't a full proof-of-concept. Lemmings is heavily pixel-based (explosions, destructable landscapes - there's a site on this too, I'll find it when I get home), so you'll probably need to know all about pixellated landscapes instead of blocks.
EDIT: I found those sites.
www.gametutorials.com has some simple C++ tutorials and the other site, currently
http://jnrdev.72dpiarmy.com/ , keeps moving around. It uses SDL (Simple DirectMedia Layer) too, so if you don't use it, you should!