If God desires salvation for all, how come many people died without hearing the gospel? 1 Timothy 2:4 states that God wants everyone to be saved:


  This is good, and pleases God our Savior, who wants all people to be saved and
  to come to a knowledge of the truth. For there is one God and one mediator
  between God and mankind, the man Christ Jesus, who gave himself as a ransom for
  all people. And for this purpose I was appointed a herald and an apostle—I am telling the truth, I am not lying—and a true and faithful teacher of the Gentiles. 


Furthermore Timothy possibly implies that Jesus also saves those who don't believe:


  That is why we labor and strive, because we have put our hope in the
  living God, who is the Savior of all people, and especially of those
  who believe.


In Ezekiel 18:23 we read:


  Do I take any pleasure in the death of the wicked? declares the
  Sovereign LORD. Rather, am I not pleased when they turn from their
  ways and live?


Ezekiel 18:32


  For I take no pleasure in the death of anyone, declares the Sovereign
  LORD. Repent and live!


Ezekiel 33:11


  Say to them, 'As surely as I live, declares the Sovereign LORD, I take
  no pleasure in the death of the wicked, but rather that they turn from
  their ways and live. Turn! Turn from your evil ways! Why will you die,
  people of Israel?'


Here is my question: it is obvious that lots of people in the world have never heard the gospel. This includes pretty much everyone living in East Asia, Australia and the Americas in the year 50 AD.

These people had NO CHANCE to hear the gospel. Yet the above verses all show that God desires all to be saved.

Doesn't that logically imply that people can be saved without coming to believe in the Gospel? After all, you can't have all three statements being true:


God desires all people to be saved
The only way to get saved is hearing the gospel and accepting Jesus
Many people never heard the gospel.


One of these must not be correct and I think it's #2.
"3. Many people never heard the gospel." Among them are people who don't want to hear about spiritual matters; they are satisfied with this life. Paul the apostle preached the gospel to the hardened Pharisees and they would not listen. They were not thirsty; they wanted life to remain as is. They heard and did not want to change. So it is with many who are satisfied with life as they know it. 

So I posit another line to add your list: 4. Among those who never heard the gospel, God reaches out to those who genuinely hunger for something more than this life. Cornelius is a prime example (Acts 10); this story specifically addresses the charge people have that you raise here. I've read writings by missionary organizations about natives coming to God this way -- that God approaches quietly, one-by-one, those who are thirsty for more, and direct them to the missionaries or the missionaries to them.

You wrote: "These people had NO CHANCE to hear the gospel. Yet the above verses all show that God desires all to be saved. Doesn't that logically imply that people can be saved without coming to believe in the Gospel?"

Those verses logically imply that people can be saved without coming to believe in the gospel. But you did not include another verse, John 14:6, which states that no one goes to the Father but through Jesus. That's why #2 is correct.  

With the addition of John 14:6, the logical conclusion changes. God desires all men to be saved. God chooses to save those who believe in Him through Jesus during and after His ministry, and possibly through faith in Himself beforehand. All three points are correct and without contradiction. 

You don't state it, but it appears that your real question is one that has been asked thousands of times: "What about those who have never heard the Gospel? Isn't it unfair that they would go to  @#!*%  when they did not have the chance to hear the gospel and be saved?" If this is your question, you should ask it. 

You wrote: "If God desires salvation for all, how come many people died without hearing the gospel?"

There are many answers to this as there are people. God doesn't force His will on His hearers. It's their choice whether they will accept the message, whether through preaching or, if they never heard, through a guilty conscience to seek relief, which God can use to draw to Himself (as I mentioned with the missionaries earlier).