The First Article, Section Four, of the US Constitution says:

The Times, Places and Manner of holding Elections for Senators and Representatives, shall be prescribed in each State by the Legislature thereof

That seems clear a state can choose whatever ‘manner’ it wishes to hold an election.
Of course the law is always open to interpretation. But it seems that constitutionally a lottery would be allowed.

Several states do already mandate a flip of the coin to settle tied local elections.