Give the ten most populous states 3 senate seats each, and the ten least populous states 1 senate seat each. Reapportion as necessary after every census. You might have somewhat unbalanced senate classes (and/or have to hold extra special elections), but that's not the end of the world.
Still not a perfect system, but it's a major improvement imo.
Except you can't change each State having the same number of Senators unless all the States agree. That's never going to happen. About the only changes that realistically could happen would be to increase the size of the Senate to 3 Senators per State or decrease the term length to 4 years so that each State elects 1 Senator per general election.
I never said it would happen.
But that entrenchment clause isn't that much of an extra barrier, since it can be amended. Since you'd have to amend the constitution to change how the senate is apportioned anyway, you just amend article five and then amend article one.
Except an argument could be made that the article 5 amendment IS, in fact, denying equal representation in the Senate, and so is impermissible under the existing constitutional provisions 
Which would be a political decision up to Congress to decide. That said, Our politics would have to be considerably more broken than it is now before an amendment to end equal suffrage of the States in the Senate would get a majority, let alone two-thirds of the Senate and three-fourths of the States. Far more likely would be an amendment to limit the powers of the Senate and make it more like the 19th century House of Lords instead of the 18th century version it is now.
This would have been a lot more likely if the popular election of the Senators had never happened. It is hard to do this when not only are senators populartly elected, but they are the only federal officials elected statewide. And, do not forget, they are the only legislators in the US that are truly not gerrymanderable.
