>At least in the U.S., lying by itself cannot be made illegal, as a violation of the First Amendment.
This isn't true. False statements of fact are a major exception to the First Amendment [0].
Besides perjury, you can prosecute people for defamation or libel. Usually it's a civil matter, but there's also criminal defamation. Finally, as WildUtah mentions below, making false statements is a crime.