I think I'd be fine with randomness plus what Skyscraper called a disaster avoidance system.
My favored approach would be a random roll system with safety nets. One character generation system that I've thought about before, but which I've never actually implemented in an actual game, would be to start with a standard array (say 16, 14, 13, 12, 10, 8 or 13, 12, 11, 10, 9, 8 if you want a lower powered game) and arrange as desired. This becomes your safety net - the minimum your character will have tin that ability score. Then, you roll 3d6 for each ability score, and if what you roll is higher than the number you assigned, your ability score increases to that instead.
So let's say you're using the 16, 14, 13, 12, 10, 8 array, and you create a fighter with Str 16, Con 14, Dex 13, Int 8, Wis 12 and Cha 10. Then you roll 3d6 for each ability score. If you roll a 14 for Str and 9 for Con, your Str and Con remain 16 and 14 respectively. However, if you roll a 15 for Dex and 12 for Int, your Dex and Int will be 15 and 12 respectively.
The advantage (IMO) to this system is that you can do your character concept planning on the basis of your "guaranteed" minimum ability scores, and if you happen to have an unexpected high score somewhere, you don't have to change your plans if you don't want to. So maybe you wanted to be a fighter and assigned a 16 to Str, but then you rolled an 18 for Intelligence. You can continue to play as a genius fighter, or you could change your character concept and play an exceptionally strong wizard, or you might decide to multiclass.
I also like Crazy Jerome's idea of self-correcting randomness in character advancement. To tie it in with the idea of guaranteed minimums, I would run it something along these lines: if the ability score you want to increase is below a certain number, the increase in automatic. Otherwise, you have to roll. I'd peg that number to the highest "guaranteed" number you could assign to your ability scores. If the highest was a 16, for example, at the first stat boost, you could increase your ability score to 17 automatically. However, if it was already 17 or higher, you would have to roll higher than that on 1d20+1. Subsequently, for the Nth stat increase, an increase to 16+N is automatic. Otherwise, you would need to roll higher than your ability score on 1d20+N.