So is it simply wrong-headed to plead for a return to Lex Rex, to the law as final arbiter and thus, in a sense, king? I don't think so. I think that the problem lies in a misunderstanding of what is meant by phrases like "a nation of laws rather than a nation of men." What is being decried is not strong leadership, decisiveness or wisdom applied by those in power. What is being decried is capriciousness. The problem is not men using the authority rightly conferred on them, but men confiscating authority to themselves in opposition to the law, which gives them their authority in the first place (apart from divine conferral).
The law is king insofar as the law sets the framework within which men are to exercise their authority. The law is a check on the whims of men, while at the same time being the foundation for the real authority they do have. The law both gives the president authority and circumscribes that authority. So kings, presidents, prime ministers and others in authority are certainly expected to render judgments, to take action, to lead in military endeavors, etc. But they are not to do so without constraint. The law is primary insofar as it stands as the fixed point. A leader's job is the right application of the law to particular circumstances. However, when a leader acts in opposition to the law, there remains no check on his exercise of power and he becomes a tyrant.
This is why so many libertarians and paleo-conservatives decried the assassination of Anwar al Awlaki. The question has nothing to do with whether Awlaki was a bad person, or even whether he deserved to be killed. The point is about what it means for a president to determine that rather than being limited by due process and the fifth amendment, he is actually in a position to decide who receives due process and to whom the fifth amendment applies. This goes beyond slippery slope argumentation. The argument is one of legal precedent. When a person in authority begins to behave as if they are the source of law and justice, and when they take upon themselves the authority to grant or withhold the very rights that have traditionally been seen as inviolate (i.e. life), and when they do so in a nation or state that has been at pains to safeguard those very rights, then what can we call it other than tyranny?