If the Senate and President wanted to pass a law, but the House of Representatives voted against it, could the President and Senate pass it by including it in a treaty with a foreign country (assuming they found a country willing to help them bypass the House)?
The leading case relevant to the question is Missouri v. Holland, 252 U.S. 416 (1920), in which the U.S. Supreme Court held that a self-executing bird migration treaty could override state law. It is also well established that a treaty may override a previously enacted federal statute.
While there might be a requirement that the treaty not be a sham that really doesn't involve another county, or otherwise have an international component, as a practical matter, meeting this requirement is something that would almost always be possible.
So, the President and a two-thirds majority of the Senate, in cooperation with a foreign country, by treaty, can accomplish legislative ends with which the House would not agree.
As a practical matter, however, the two-thirds majority requirement for passage of a treaty in the Senate, the partisan organization of politics in the U.S., and the correlation of the partisan makeup of the Senate and the House, means that this observation is basically an irrelevant footnote.
No treaty that could secure bipartisan support by two-thirds of U.S. Senators, and also be signed by the President, would not be able to be passed in the House. There has never been a time in U.S. history where one political faction has a two-thirds majority in the Senate and another political faction had a majority in the House. As a practical matter, it is almost always easier to pass ordinary legislation approved by majorities in the House and Senate, than it is to pass a self-executing treaty.
The only scenario I could image where this might happen would be one in which an "old guard" President and Senate are in place, and then one election, some new political movement suddenly nearly sweeps the House and the U.S. Senate seats that are open due to some pivotal historic event, but there hasn't been more than a single Senate election or a Presidential election since that sea change in public opinion, something that very rarely has happened in other countries.
It depends on the wording and topic of the treaty. Some treaties are considered self-effectuating but others are not. If provisions are not self-effectuating, domestic law must be enacted for those provisions to be in force. The quote below is from the Congressional Research Service. There may be new developments since 2018.
International Law and Agreements: Their Effect upon U.S. Law Stephen P. Mulligan Legislative Attorney Updated September 19, 2018
Some provisions of international treaties or executive agreements are considered “self- executing,” meaning that they have the force of domestic law without the need for subsequent congressional action. Provisions that are not considered self-executing are understood to require implementing legislation to provide U.S. agencies with legal authority to carry out the functions and obligations contemplated by the agreement or to make them enforceable in court.
The Supreme Court has deemed a provision non-self-executing when the text manifests an intent that the provision not be directly enforceable in U.S. courts or when the Senate conditions its advice and consent on the understanding that the provision is non-self-executing. Although the Supreme Court has not addressed the issue directly, many courts and commentators agree that provisions in international agreements that would require the United States to exercise authority that the Constitution assigns to Congress exclusively must be deemed non-self-executing, and implementing legislation is required to give such provisions domestic legal effect. Lower courts have concluded that, because Congress controls the power of the purse, a treaty provision that requires expenditure of funds must be treated as non-self-executing. Other lower courts have suggested that treaty provisions that purport to create criminal liability or raise revenue must be deemed non-self-executing because those powers are the exclusive prerogative of Congress.
Limits on the subject matter of a treaty are not specified in the Constitution, so we don't know how the Supreme Court will rule, were this to happen. This note tells us what little the court has said. One view is that they are to be limited to "matters of international concern", another is that everything is to some degree a matter of international concern. See also these opinions and these.
Obviously, the law would have to pass basic constitutional muster. I suspect that a "typical" law that directly creates or modifies part of the US Code would not be possible. There is a distinction between self-executing treaties which a court can directly enforce, vs. a treaty which requires congressional intervention in the form of passing enabling legislation (hence requiring House consent). This distinction was made long ago in Foster v. Neilson, and in the case of a non-self-executing treaty Justice Marshall wrote that "the treaty addresses itself to the political, not the judicial department; and the legislature must execute the contract before it can become a rule for the Court".