There was a project for a while around implementing a national popular vote without a constitutional amendment (I think this is it). Since states are free to apportion electoral votes as they see fit, a national popular vote just requires that states controlling a majority of electoral votes commit to give all of their votes to the winner of the popular. Under the project setup, states individually pass bills committing to go along with this scheme as soon as enough other states agree to it.
I think that project has the right general approach - tackling the problem state-by-state, achieving a simple majority, and routing around the challenge of a constitutional amendment. The problem is that the states with a relative advantage under the electoral college probably won't want to give that up. And you will need the support of those states - precisely because they control an outsized portion of electoral votes!
What we really need is a setup that makes the national popular vote a Nash equilibrium. States with extra electoral votes need to be able to gain an advantage if they agree to a popular vote, but other states don't. So the trick is to set up a deal between two (or more) states, which puts them at an advantage relative to other states. I haven't figured out a perfect way to do it yet, but I may have a solution which is good enough.
Here's the idea (there are others): rather than a state allocating their electorals to the popular winner iff enough states agree, how about a state allocates all of their electorals unconditionally to the winner of the popular vote among states which have agreed?
Say, for instance, Alaska decides to form the "Alaska voting block". All of Alaska's electoral votes go to the winner of the popular vote within the block. Any state can join the block by agreeing to the same terms: all of their electoral votes go to the block winner. So now California comes along and is like "hey, we can pick up 3 electoral votes basically for free by joining Alaska's voting block. Let's do it." And then Texas takes a look and says "you know, California's popular vote is actually pretty split... we could swing the popular vote of the Alaska block if we join." And then New York hops on board. And so on. Pretty soon, the Alaska voting block is the dominant factor in an election, and all states need to join in order to have any say at all in the election.
To make this happen, you only need to pass a single bill, in a single state, and it doesn't even matter which state. Plus, whichever state is first gets to name the voting block!