This seems like a huge problem for many smashers. I like this topic idea. Hell, I have trouble with it sometimes.
I sometimes make a huge list of possible approaches and combos in all situations (not just the most effective ones). I then look over my old matches via replay (one of the best additions to brawl. :3) and see what I ACTUALLY do in the situations. I usually actually only use very few ideas from my list. ;=; Later, I make a conscious effort to add to my repertoire from the list.
I also try to occasionally pull random **** out of my *** in friendlies to see how a human will respond. Sometimes, even the most useless of all moves can work if done in the right situation (mindgaemz, if you will). Hell, some moves even have a sort of mental effect on your opponent, as stated by a certain Ike guide, as well as via experience. Throw out a random Ike Fsmash or two at 50% after a long barrage of quick attacks, and you might actually hit with it as they were most likely expecting another quick attack and leap at you, thinking that they've finally found an opening. I wouldn't do this regularly against the same person, but it DOES work on occasion. It's why so many people always fall for the Falcon Punch about 8 times the first tine you play them. :D
Anyways, back to unpredictability. In Friendlies, try pulling random crap out of your *** and start to experiment with things that might work but you've never tried. Like doing a down-angled, Short-Hop Boomerang with Link from mid-range instead of a regular Short-hop aerial. Just remember that the key to mix-ups is that they each should have different counters, and if they try to do the wrong counter, they'll get hit. For example, with Link, "mixing up" a short-hop nair with a short hop bair won't do much for you, as either way you won't hit if they shield or spotdodge, and they can most often outprioritize both. However, mixing up a SHNair with a well-spaced SHFair will outprioritize most moves thanks to the disjointed hitbox, and sometimes keep you safe from a shieldgrab or many OoS moves, while it can still be shielded and spotdodged, though, in which case a Nair lasts so long, you can sometimes even hit them as they come out of it if they spotdodge early, or quickly FF and attack before the spotdodge ends if you anticipate it. Meanwhile, you can even Zair from a distance away to eat at their shield if they anticipate it, and you're completely safe from a shieldgrab or most OoS moves.
Link's Nair, Fair, and Zair is a viable mix-up, I believe.