You can do this as:
order by (col like 'lead_%') desc,
rand()
The expression (col like 'lead_%')
returns either true (treated as 1) or false (treated as 0), so the desc
puts the matches first. The rand()
is just because you say you want things ordered randomly. This will order both groups randomly.