I unlocked everything by completing all the challenges. B/C from my experience on the AW I know that it was almost impossible to get the proper midboss. Most times I always ended up fighting Gai.
The throw break challenge was pretty easy. All you gotta do is be prepared to hit F+either C or D when approaching the opponent. And you get a whole "round" to do it.
Here is my SUPER easy way to complete challenge #34:
Shen (leader)
King
Iori
The characters need to be picked in that order. At the start of the round activate Shen's LDM, then jump D, close C, Fw+B, qcf+C (SHIFT to King) jump in D, close D (1-hit), Df+D, rdp+B (4 hits), super cancel into qcf, hcb+D, (SHIFT to Iori) jump in D, close C, dp+C super cancel into qcfX2+C.
The best part about that combo is that Shen does over 50% of the damage by himself. I also have another one that is a little harder.
Ryo
Robert
Gato (leader)
Starting with Ryo. hcb,f+K (new move) super cancel into qcf, hcb+C (SHIFT to Robert) jump in D, close C, Fw+B (the step kick), qcf,hcb+C (SHIFT to Gato) jump in D, close C, qcf+A, super cancel into qcfX2+A, DREAM CANCEL into dp+e 3 times.
That one is a little harder b/c the SHIFT~jump in attacks have to be timed really well and the timing on the Robert portion is trick to get the Close C, Fw+B. Also the Gato part is REALLY tricky b/c if you dont instantly get the special into the super cancel you wont do enough damage on the DREAM CANCEL.
O.