I'm trying to start doing this (in the style of Frusciante, Hendrix, etc) and I've found some good videos, but my problem seems to be a lack of precision/strength/flexibility or something in my left hand. Does anyone know of any exercises to build up the left (fretting) hand?
Keep up those chords. If you've got something you want to play but you can't for technical reasons, the best exercise is that passage. Keep practicing your chord shifts and different suspensions and whatnot.
When you say embellishing, I'm assuming that your refering to adding notes, legato, and short melody phrases while in a barre form. If you know most of the barre chord forms, then it is matter of building up the dexterity of 2nd, 3rd, and 4th fingers. Make up routines holding the first finger barred using the other fingers to play notes up the next three frets (even better, 4 frets), forwards, backwards, intervaly. Then do the same for legato.

Precision comes will slow careful practice and the strength will come will follow as long as you keep practicing.
I'm the only player to be sponsered by 7 guitar companies not to use their products.
I say dont use a bar.

The common thing doe in this situation is to play with your thumb over the top of the fretboard to fret the low E, ignore the A string, and playing the rest of the chord.

This will give your fingers more freedom to move and do the embellishments.

This is what Hendrix did.

You can also just play simple triads.