So, you want it random, but you don't really want it random, in a sort of vague, unspecified way.
Can you do this in MATLAB? NO! The vagueness makes that impossible. What might you do? God only nows, because you have been too vague to know for sure what would be acceptable.
Can you rank the various conditions into 8 distinct ranks of difficulty? (If not, this is still not a problem. 4 levels of difficulty are still ok.) For now, I'll assume there are 8 ranks.
So a trial with difficulty of -7 is REALLY easy. A +7 is the most difficult.
Now, consider a simple random permutation of the trials. Think of this as a zero sum random walk. At the very end, you know it you will return to zero, since sum(trials)==0.
What you don't want (I THINK) is a sequence of trials that spends the entire sequence a long way above or below zero. In fact, the one I plotted above is actually pretty good, compared to several that I tried. On the other hand, I only had to take a few random permutations until I found something that seemed pretty good.
The point being, you can do the same. You could even create some measure of the random walk that I show above so that random walks that wander too far away from zero are bad. Then just set up a while loop that will iterate until you find a random permutation that satisfies your goal of acceptability.
If you can only form 4 ranks of difficulty, then set the trials as having difficulty as
T = [-3 -3 -1 -1 1 1 3 3];
Now take random permuations of that set until you are happy with the cumulative random walk induced by the permutation.
If you want something better than this, then you probably need to be VERY, VERY less vague.