Our knowledge of Norse beliefs about the afterlife is somewhat filtered by the literate Christians reporting on it, in some cases quite a while after the actual Vikings. So there are several possibilities:

1. Maybe the Norse didn't really have much of a logic to their afterlife, and a skilled or lucky warrior really did go to Hel as you suggest; and this didn't bother them because their religious life really wasn't that focused on the afterlife. This is alien to people from a Christian tradition, but (to oversimplify for the sake of a short answer) many "pagan" religions are more concerned with purity and ritual in this life, rather than what happens after death.
2. It is sometimes reported that to wound yourself with a spear on your deathbed was sufficient; perhaps the Valkyries weren't all that picky. (After all, the ice giants are coming - just how elitist do you want to be, when it comes to recruiting fighters for Vigrid field?) So maybe the Norse did think of that problem, and invented a loophole.
3. Maybe the Norse actually had a rich and self-consistent tradition for the afterlife, with people who had done a lot of sacrificing to Frey going to a land where the farms are forever giving back forty-fold harvests, and there is no war; and women going to his sister and each ruling a great household and having forty keys on their belt... and what the chroniclers wrote down is "Warriors to Valhalla, everyone else to Helheim!"

The sources for learning about Germanic religion are actually rather broad.

• Literary sources - these are the main things that get talked about during questions like this. The Eddas, Poetic and Prose; the Sagas, Poetry, etc. These tend to be very dense, as literature tends to be, particularly Poetry, which is deeply, deeply steeped in a system of symbols that most people alive today just don't share. Concepts that could be conveyed as an aside, or a throw away line, baffle and shock us, much in the way that one can today, or at least in this sub, call someone a Quisling and it be completely understood; a thousand years from now, the story of Quisling may largely be forgotton, so that the aside makes no sense. There's a lot more to say here, but I'd like to stay somewhat brief in this post.

• Contemporary First and Second hand accounts. We have several contemporary accounts from history that discuss Germanic religion. The most famous to a laymen these days would be Ibn Fadlan's account of a Rus burial, complete with animal and human sacrifice. This account forms the framework for the film The 13th Warrior, hence why you may be familiar. Other contemporary accounts include Cornelius Tacitus, a Roman living in the late [EDIT] 2nd Century who wrote what might almost be called an ethnography (I'm being charitable) of the Germans, largely based on interviewing native Germans about their homeland. It is, at best, a second hand account. That said, there are things mentioned in Germania that have been found in the physical record (more on that in a second). The last group of "Contemporary Accounts" I'm going to group into a heading I affectionally call "Those Damn Bloody Heathens" diatribes. This consists of post conversion law codes, sermons, history (Venerable Bede, Saxo Grammaticus) and other polemics that attacked what was looked upon as Pagan Practice. While completely biased, if you read with a critical eye and acknowledgement of those biases, you can learn a lot from "The Damn Bloody Heathen" Diatribes.

• Archaeology. There is a tremendous wealth of physical evidence available to us: Sacrificial deposits, Bog Bodies, Graves, Community sites, etc. There, you can find evidence from the past that correlates what we learn from Literary and Contemporary sources, allowing us to say with greater confidence about things like Sacrifice.

• Comparative Religion. This one is going to be a controversial topic, and I only mention it here for completeness sake. The Germanic, Latin, Greek, Sanskrit, all come from a mother tongue called Proto-Indo European. Language is the vector for culture. As language changes, so does culture. But as language changes, one can still trace its ancestry backwards and see how it relates to other languages, and from that, reconstruct a proto-language, shared by each of the others. While I personally find the topic fascinating and capable of real insight, I'm not going to use it today in deference to staying 'within discipline.'

Now, having listed the sources available to us to get a sense of Germanic / Nordic religion, I think it is important to emphasize that Valhalla itself is relatively restricted to Literary Sources, and in particular, the late Nordic sources of the Elder and Prose Edda. Here are things we do know about Valhalla, and some conclusions we can draw.

1. Valhalla is deeply tied to the Odin cult in particular. Odin's influence increased over time, and eventually, he supplanted *Tiwaz (Tyr, Tiw, etc) as the preeminent god of the Germans sometime around the Late Bronze, Early Iron Age.

2. Odin is listed as the progenitor of Kingly lineages in England, Continental Germany, and Scandinavia, with some notable exceptions.

3. Snorri, the compiler of the Eddic poetry and author of the Prose Edda (along with other books) was himself a Christian. His purpose in compiling these tales was to preserve a poetic form in the Court of a King who was educated in the Classical Schools and grew up with steeped in the semiotics / symbolism of the Greek and Roman world. His purpose here wasn't to preserve the symbols of the ancient religion, but rather the art form, which relied on those symbols only in a superficial way.

I have up until this point, tried my best to avoid speculation. From here on out, I'm drawing on the framework above, as well as the works I'm citing below, to propose this idea: All writers will, to greater or lessor extent, write to their audience. A letter to a young man is not going to read the same as this comment, or when I write business communication during my day job. Academic writing is not the same as informal communication. So on some level, Snorri Sturluson was writing to a King, about a Kingly Art. In it, he would emphasize the Kingly God, and those things that would cater to that audience. Again, his purpose was never to preserve the ancient religion, but rather the mythology and art form he loved. With that in mind, I think it is safe to say that the afterlife as presented by Snorri is particularly limited, and only tied up with the Kingly Power that was his audience and purpose in writing. Valhalla was neither the beginning, nor the end, in how the old pre-christian Germanics looked at the afterlife.

On semiotics, on the worldview and the way that Non-Christians tend to perceive the world somewhat differently than Christians do, I'm going to recommend the following works:

• The Semiotics of Fate, Death, and the Soul in Germanic Culture: The Christianization of Old Saxon (Berkeley Insights in Linguistics and Semiotics). By Priscilla Augustyn

• The Germanization of Early Medieval Christianity, by James C. Russel

• The Saxon Savior, by G. Ronald Murphy.

• Culture of the Teutons, by Vilhelm Grönbech.

On interpreting Icelandic Literature, on the conversion of Iceland:

• A Piece of Horse Liver, by Jon Hnefill Aðalsteinsson

• Under the Cloak, by the same.

There's more. So Much more. This topic is a bit of a passion of mine.

Norse belief wasn't as cohesive as Christianity for example. While they all shared the same basic belief and gods, the stories and such would vary from place to place, more of a tradition than a religion. There are references to people cutting their bodies before death to trick the Valkyries into believing they died in battle, old warriors seeking death in battle and also the idea that death in battle wasn't enough. The principle is that only the best of the best would be picked to form the army that would defend Asgard when Ragnarok came, so there's also the notion that only warriors of particular renown, perhaps ones followed by Odin himself, would make it.

We have to remember though that Valhalla wouldn't have been viewed like heaven. It is a place where you would fight and possibly die every single day for thousands of years, that kind of thing didn't appeal to most people. Folk beliefs on the afterlife varied locally, ranging from going to the halls of your ancestors, going to Helheim (who's nature varies from the Christian Hell to somewhere that isn't actually that bad), going to the hall of a particular god, to the idea of nothingness. Some believed most people went to Ginnungagap, which is basically just an abyss, nothingness. This may have been a way of saying that "when you're dead, you just die".

Norse Paganism is an interesting religion because, really, it's barely a religion. It doesn't impose rules like we're used to from Abrahamic religions, and the difference in beliefs from one location to another in the same religion are probably more different to each other than Protestantism and Islam!