Well, Vice President Johnston did still receive a plurality of support from Democratic states in 1840, so there could be a candidate that received a majority anyway...but this doesn't make a difference in the pre 1900 era and we have 1872 as a good rule to look at for precedence.
If a party is particularly on the ball they would rally behind a single candidate to go on the ticket at the top for their electors to support for President and the issue is settled on that front. The easiest person would be whatever VP candidate got the most support. If they are not on the ball, as evidenced by the inability to pick a VP candidate, then the electoral college will have no majority. The top three candidates, almost certainly the runner up from the other party and then the two guys from the winning party that got the most support, go to the House in a contingent election. If no one from the winning party gets a majority support as VP in either scenario there will also be a Senate contingent election amongst the top two vote getters which will be between the guy from the losing party and the guy with the most votes from the winning party.