All-Star is a weird mode. I remember a friend of mine said that the mode "rewards you for playing like a five-year-old": in other words, if you just spam strong smash moves every chance you can, you will probably do quite well.
Heavies walk all over this mode. I'd prioritise beating it with characters like Bowser and Ganondorf first, since that will get you into the swing of it and you'll know what strategies work best. What I find helpful for heavies is to bait as many opponents as you can into a group and then punish them with your most efficient smash move: in this case, you want a move that's relatively quick, does decent knockback and can preferably hit multiple targets at once. Moves like Bowser's u-smash / f-smash, Ganondorf's fs-mash / d-smash, Ike's u-smash and DK's u-tilt / d-smash work wonders.
It gets trickier when you move onto smaller or more projectile-based characters. Characters with weaker moves can get trounced in this mode, so you want to play as cleverly as possible whilst minimising damage. If you're playing a character that can cheese out a victory with projectile spam, then do just that: there's no honour in All-Star, anything that helps you win is a valid tactic. When I cleared All-Star with Duck Hunt on Hard to beat the in-game challenge, I managed to eke out a relatively comfortable win with flagrant neutral-b spam and rolling to the distance whenever the opponent got too close. For characters with weak melee options, minimising damage becomes paramount. Whereas there's a certain berth of safety with heavies, if your character can get KO'd at about 50%, you want to make sure your top priority is damage evasion. Projectile-based characters can do this by staying at a comfortable distance, whereas faster characters may benefit from hit 'n' run tactics for best results. Don't worry about running out the clock: it resets between matches, so there's very little chance that you will be caught out by it.
Quick comment here: my brother reckons this challenge is easy with Robin, since you can abuse Nosferatu to heal damage if you need to. Your tomes are reset between matches, so feel free to go ham if you want! Just remember that heal naturally (e.g. Wii Fit Trainer's Sun Salutation and Deep Breathing) don't work in the lobby.
It's important to know when to heal. Because you need to rely on a handful of healing items, each with different strengths, it's good to understand when you will get the best use out of each. Maxim Tomato heals 100% damage, Fairy Bottle heals 100% if your damage is over 100% when you use it, Heart Container heals all damage. I usually wait until I'm in the red zone (between 80 - 100%) before I use an item, more if my character is heavier and can take a few hits. I usually try to save a Heart Container for the final match if I can, since it means I don't have to worry about getting KO'd at the last second and I can concentrate on patiently clearing the game. It's a good idea to prioritise saving an item as a contingency, but if you think the risk is too much to chance the game on, then by all means do what makes you more comfortable. Do bear in mind that, especially for heavies, it can be good to keep a bit of damage under your belt to increase your rage: when you play a few times, you can figure out how best to balance the risk / reward ratio of the game.
Finally, stages are important. If you can get a stage like Mario Galaxy or Colosseum in the first round, you're off to a good start, since you can abuse the walkoff to get some cheap, risk-free KO's. Kono Jungle 64 is a good stage too, since the wide blastzones can offer you some breathing room midway through the game, while Luigi's Mansion is my favourite stage for the final match, since the caves of life in the bottom corners can help you survive even if you're at high percents while you build up damage and get the KO.
Most importantly, practice! You will inevitably get bodied a few times, just keep at it and you will eventually work out a system that works for you. There's no "press to win" button, just hard work and determination. Hope this helps!
.
