Before Marbury v Madison, how did the court system (or other function of government) invalidate laws that were unconstitutional?
Prior to Marbury v. Madison no laws were invalidated as unconstitutional by any government body.
During consideration of a proposed law, in the House, the bill would go through the Committee on Detail, the Committee on Style, and the Committee of the Whole. The proposal would be vetted for compliance with the Constitution, as interpreted by the members of the House. Any member could object on Constitutional grounds, at which point the members would vote on the objection.
In the discussion of Bounty Payments for Cod Fisheries, 6 February 1792, James Madison objected to the use of "bounty" and to the use of the (so-called) General Welfare clause as Constitutional authority. The vote was against Madison's objection.
[It is likely that the Senate also did such vetting; but at that time, all deliberations by the Senate were conducted in secret.]
The Sedition Act, in particular, violated freedom of speech in the First Amendment. The Act was allowed to expire.
The Alien and Sedition Acts:
Lastly, the controversial Sedition Act restricted speech that was critical of the federal government. Under the Sedition Act, the Federalists allowed people who were accused of violating the sedition laws to use truth as a defense. The Sedition Act resulted in the prosecution and conviction of many Jeffersonian newspaper owners who disagreed with the government.
The acts were denounced by Democratic-Republicans and ultimately helped them to victory in the 1800 election, when Thomas Jefferson defeated the incumbent, President Adams. The Sedition Act and the Alien Friends Act were allowed to expire in 1800 and 1801, respectively.
Wikipedia, Freedom of speech and of the press:
Wording of the clause
The First Amendment bars Congress from "abridging the freedom of speech, or of the press...." U.S. Supreme Court Justice John Paul Stevens commented about this phraseology in a 1993 journal article: "I emphasize the word 'the' in the term 'the freedom of speech' because the definite article suggests that the draftsmen intended to immunize a previously identified category or subset of speech." Stevens said that, otherwise, the clause might absurdly immunize things like false testimony under oath. Like Stevens, journalist Anthony Lewis wrote: "The word 'the' can be read to mean what was understood at the time to be included in the concept of free speech." But what was understood at the time is not 100% clear. In the late 1790s, the lead author of the speech and press clauses, James Madison, argued against narrowing this freedom to what had existed under English common law:
The practice in America must be entitled to much more respect. In every state, probably, in the Union, the press has exerted a freedom in canvassing the merits and measures of public men, of every description, which has not been confined to the strict limits of the common law.
Madison wrote this in 1799, when he was in a dispute about the constitutionality of the Alien and Sedition Laws, which was legislation enacted in 1798 by President John Adams' Federalist Party to ban seditious libel. Madison believed that legislation to be unconstitutional, and his adversaries in that dispute, such as John Marshall, advocated the narrow freedom of speech that had existed in the English common law.
Speech critical of the government
The Supreme Court declined to rule on the constitutionality of any federal law regarding the Free Speech Clause until the 20th century. For example, the Supreme Court never ruled on the Alien and Sedition Acts; three Supreme Court justices riding circuit presided over sedition trials without indicating any reservations. The leading critics of the law, Vice President Thomas Jefferson and James Madison, argued for the Acts' unconstitutionality based on the First Amendment and other Constitutional provisions. Jefferson succeeded Adams as president, in part due to the unpopularity of the latter's sedition prosecutions; he and his party quickly overturned the Acts and pardoned those imprisoned by them. In the majority opinion in New York Times Co. v. Sullivan (1964), the Court noted the importance of this public debate as a precedent in First Amendment law and ruled that the Acts had been unconstitutional: "Although the Sedition Act was never tested in this Court, the attack upon its validity has carried the day in the court of history."
The Whiskey Tax, an excise, violated Article I, Section 8, Clause 1, which requires that excises be uniform. Large distillers paid a lower rate than small distillers. The law was repealed.
To lay and collect Taxes, Duties, Imposts and Excises, ...; but all Duties, Imposts and Excises shall be uniform throughout the United States;
Under the new law, large producers paid the tax annually at a rate of six cents per gallon, and the more they produced, the further the tax breaks.
Small producers, however, were stuck with a nine cents per gallon rate. Farmers took further issue because only cash would be accepted for tax payment.
The whiskey tax that inspired the rebellion remained in effect until 1802. Under the leadership of President Thomas Jefferson and the Republican Party (which, like many citizens, opposed Hamilton’s Federalist tax policies), the tax was repealed after continuing to be almost impossible to collect.
THE CONSTITUTION of the UNITED STATES OF AMERICA, ANALYSIS AND INTERPRETATION, page 2327 (PDF page 2353).
ACTS OF CONGRESS HELD UNCONSTITUTIONAL IN
WHOLE OR IN PART BY THE SUPREME COURT
OF THE UNITED STATES
Act of September 24, 1789 (1 Stat. 81, § 13, in part).
Provision that “[the Supreme Court] shall have power to issue . . .
writs of mandamus, in cases warranted by the principles and usages
of law, to any . . . persons holding office, under authority of the United
States” as applied to the issue of mandamus to the Secretary of State
requiring him to deliver to plaintiff a commission (duly signed by the
President) as justice of the peace in the District of Columbia held an
attempt to enlarge the original jurisdiction of the Supreme Court, fixed
by Article III, § 2.
Marbury v. Madison, 5 U.S. (1 Cr.) 137 (1803).
Act of February 20, 1812 (2 Stat. 677).
Provisions establishing board of revision to annul titles conferred
many years previously by governors of the Northwest Territory were
held violative of the due process clause of the Fifth Amendment.
Reichart v. Felps, 73 U.S. (6 Wall.) 160 (1868).
One hundred eighty other acts omitted.