I could see a Madman Trelaine type character, dark, even more unhinged, darkly comic at times but able to bring the threat.
That said, I am sorry, but Trelaine is a TV only character to me. He is not,even rebooted, strong enough to carry 100 million dollar budgets to the stars, IMO.
Now Del Toro as a bloodthirsty Klingon with designs on some evil thing, maybe.
I think a real problem exists now for the writers because how do you top Red Matter, a do all device, and destruction of a Key story element (Vulcans and Romulans) and still have magnitude. What makes introducing new elements easier on TV is the regularity of exposure to the key personalities and character devices. Lose that and do a movie every 3 years you could change the names of the principal characters and call it WarpStar and have a movie. Familiarity with a little newness works on that time interval, again IMO.