So, Dedede wants to team with a strong punisher?
So that would leave...
Bowser (Very poor recovery)
Captain Falcon (poor recovery)
Donkey Kong (poor recovery, but I see this being one of our best teammates. SETUPS TO NINE PUNCH.)
Falco (maybe, meh recovery at best, landing FSmash shouldn't be to much trouble)
Fox (meh recovery, but dat USmash. On a stage like Halberd, serious danger)
Game and Watch (bucket braking to live forever, Dedede effectively removes an option from DThrow techchase by being there. Unless they want to either get UTilted or grabbed)
Ganondorf (does so much damage, so much knockback, his projectile trouble is helped by waddle dees, he can use them for lingering DAir and Wizkick hitboxes. Oh, and I guess lingering Warlock Punch if you're ballsy)
Ice Climbers lol, maybe, but probably not. Though having them shut someone down and then you keep away the other person...
Ike (no recovery to speak of, but he kills at like 12%)
King Dedede (I see this as being more silly than anything)
Kirby (some kill power, probably not optimal, but he does recover)
Link Doesn't really have kill power other than DAir, and he doesn't recover ever.
Lucario (definitely not optimal, poor recovery, needs lots of damage before he kills)
Luigi (SHORYUKEN! And a pretty good recovery. Another top contender.)
Marth (poor recovery, but things die when tippered)
Metaknight I see him interfering too much. Also, I hate him.
Ness (REALLY bad recovery, but I'd totally pay money to see setups to PK Flash.)
Pikachu (Thunder, always recovers, that's about it.)
Pokémon Trainer (all three have poor recovery, but they can kill. Stamina might get in the way.)
Snake (trash recovery, but he's Snake. He UTilts you from a mile away.)
Toon Link (doesn't really kill, but he racks up damage really fast and just generally disrupts people, making it easy to get something silly like Dash Attack.)
Wario (lives forever, one of the best recoveries in the game, kills so well)
*stops*
Ugh, this is silly. I see like 80% of the cast working.