What about if they make the act of picking random? I think I mentioned Diablo 3 before, but for those not aware, here's roughly how it would translate (in my mind):
1) You're leveling up a blue rune. You hit level 3 and it is going to add stats to one of your already present tertiaries - I honestly have no idea how this should work. You just get to pick? Or you can pick "Random" which is free but randomly assigns, or you can choose a stat for a certain amount of Gold and Runicite? Maybe if you pick a stat more than once in a row (e.g. you're leveling up an orange rune and you choose the same tertiary every time) the cost increases each subsequent selection?
2) You're leveling up a green rune. You hit level 6 and you get a new tertiary. Instead of it being completely random, you get 3-5 (or whatever number) randomly selected options and you can pick which one you want. This would still keep some randomness (especially with how many options there are) involved in the process instead of simply picking and choosing what you want. If you don't like the 3-5 you got, you can choose to reroll them for a cost - Gold and Runicite. Each time you re-roll, the cost increases.
3) You have an orange rune that is level 12. You decide that instead of having Electric Damage on your Medusa rune, you want something else. You select that tertiary and, for a cost of Gold and Runicite, you can re-roll it (same process as #2). Each time you reroll, the cost increases.
I like the idea of doing Gold/Runicite since we need more gold sinks and runicite makes sense since you're updating a rune (and I know top level players have more runicite than they can use). Using gold/runicite would also limit, I think, the amount of players complaining that it's a P2P feature only if the cost was in diamonds. Both runicite and gold can be purchased via diamonds, and I think both of those features are underutilized right now.
The increasing cost would be good because it would allow you to potentially get something useful for a small fee, but finding the perfect stat might be quite expensive.