A hopefully not-too-long not-too-short background
The bicameral legislature of the USA occurred as an early compromise among its founding fathers, between those who believed in individual ownership of governance [where comparatively more power ends up vested in more-populous regions] and those who believed in states’ ownership of governance [comparatively more power vested in smaller regions]; the compromise was just “nothing becomes a law unless both groups can agree on it.” The Senate gives each state two votes; the House presently attempts to give each subset of N people one vote for some N by using a census to divide each state into districts where each district, hopefully having around N people, runs a first-past-the-post election.
The danger of gerrymandering by those who draw the district lines is one reason to avoid such a system, but since the Senate seems to have a similar 50% Democrat/50% Republican deadlock it is probably not the cause of the dysfunctional US government. Indeed it rather seems likely that this process of splitting a country into segments that each run first-past-the-post elections leads inexorably to dysfunction and then civil war, and one can even view the US Civil War as having been ultimately caused by this by looking at the partisan divisions beforehand. First-past-the-post schemes contain a well-known spoiler effect where voting for a third party who better represents your interests can ultimately cause your interests to be more-poorly-represented; in this context it seems that there is a mathematical fixed point where a country contains two fixed polities who each vote passionately for one candidate, not because they support that candidate, but because the other polity terrifies them. (“If they didn't vote for a lizard, the wrong lizard might get in.”) Viewed this way, while slavery was the casus belli of the US Civil War, one might reasonably assume that if some sort of agreement had been reached about slavery, the US would have still had a civil war, just some years later over some completely different issue that sparked the powder keg.
Changing the House
Unless the USA wanted to revisit the earlier compromise, the states would still occupy one chamber and it would be hard to do elections for that chamber other than first-past-the-post (although I can't see anything in the 17th Amendment to the US Constitution that would block instant-runoff or approval voting or so).
However several nations seem to be more robust against this sort of problem through party-list proportional representation where the people vote on parties rather than individual officials, and those parties receive a proportion of the final elected officials.
The US Constitution is much more lax about the composition of the House, stating only that:
The House of Representatives shall be composed of members chosen every second year by the people of the several states, and the electors in each state shall have the qualifications requisite for electors of the most numerous branch of the state legislature.
[...age, citizenship, residence...]
Representatives and direct taxes shall be apportioned among the several states which may be included within this union, according to their respective numbers, which shall be determined by adding to the whole number of free persons, including those bound to service for a term of years, and excluding Indians not taxed, three fifths of all other Persons. [...] The number of Representatives shall not exceed one for every thirty thousand, but each state shall have at least one Representative [...]
This last paragraph was modified in detail but not in spirit by the 14th Amendment.
Most proportionate allocation systems can be modified to allocate simultaneously over both states and parties. Am I correct in understanding that as long as a proportionate representation system also distributed representatives in the House proportionately among the various states, that no constitutional amendment would be needed to make the switch?
[Clarification: I would prefer a system where all the states pool delegates, decisively refuted by Joe below, since the above suggests it would be further from the spoiler effect and hence more stable: but if each state had to perform its own party-list-proportional election I think that would also fulfill the criteria of “a proportionate representation system [that] also distributed representatives in the House proportionately among the various states.” The real question is where the laws are which require single-representative districting: whether they have fundamental or federal or state status.]