I believe the best way to address your question is to take apart what you've written, and address it piece by piece, looking especially at the assumptions you have made going into your argument. Please understand that while you may not agree with many of the statements I will make here, they do represent a Christian perspective. In particular, I will be writing from a Reformed Protestant perspective, and using some of their language. Most of the major concepts can be found in many other Christian traditions as well, although the presentation and emphasis varies. Also, you will not find unanimous agreement on these points, as many conflicting ideologies make a claim to be Christian. At some point, you must dig into the evidence and decide who's holding the picture right-side-up. I don't claim to have everything right, but I do claim that the following major points both answer your question and represent the way the world really is -- that when you look at the world this way, you suddenly find the view is in focus.
Let's start with your first point:
"God is love"
This is true. However, the definition and nature of love is often misunderstood in secular culture, and the theological claim that God is love must be understood inside the context of what else we understand about the nature of God. Most importantly, in order to love, one must also hate. Love is a defining feature of God, but in order to love a good thing, one must hate whatever is opposed to that thing. You cannot love Jews without hating the Holocaust. You cannot love babies and not hate when they are murdered. You cannot love good without hating evil. You cannot love righteousness without hating sin.
This brings up an issue you skipped over in your second point. 2 Thessalonians 1:6 deserves a little attention before we move on to the merciful bit you emphasized:
"God is just: He will pay back trouble to those who trouble you"
The justice of God is a big topic, but it strikes at the heart of your question. You ask, "How could a just God do something unfair?". Christianity's answer is that he did not. What God does is entirely fair, and he even explains why. Even the second part of this verse has a clue about what's going on. He groups men into more than one category. The verse is NOT addressed to all of humanity. It is addressed to a group of believers -- in this case, a specific gathering of believers (or church). With this in mind, you can see -- even in the fragments of text that you quoted -- that God treats some people one way, and some people another.
Your question goes on to emphasize the ways God shows compassion. For example, you used Deuteronomy 4:31:
"[God] will not abandon or destroy you or forget the covenant with your ancestors..."
Even here, I hope you see a hint of the answer. That covenant he references wasn't something God made with humankind, it was something he made with a subset of the human race. Originally, this promise was focused around one line of family descendants (Abraham to Isaac to Jacob etc.). Through history, you can trace this promise that is now open to a much broader swath of humanity -- namely, all of those that, through Jesus, have been adopted into that same family.
So let's move on to your issue with John 14:6:
"being a good person [...] is not enough"
This highlights the biggest piece of the puzzle that you are missing. There are no good people. None. Anywhere. From Adam, right on down the line to you and me, all have sinned and missed the mark, fallen short of the standard of what a good person must be in order to qualify to be accepted by God. All, that is, except one. Jesus Christ. The thing that is most emphatically different about Him is that He was without sin.
Let's stop there, and go back to 'fairness'. One of the core tenets of the Christian faith is the unapologetic claim that ALL MEN, having trespassed against God, justly deserve His wrath. In fact, it would be unjust of God to not punish all men. In this sense, to be merciful would be a disgrace to justice. So how can God also be merciful? For that, we go back to Jesus.
Jesus satisfied the divine demands of living a 100% sinless life, then He surrendered Himself, and was made to be sin in our place. Having rightly deserved everything we do not, He took on Himself the iniquities of men, and was punished for them. The wrath of God was emptied upon him. Forget the cross and the Romans and the whips and the crown of thorns for a minute, because those were only props -- hints and clues at what the real story is about. He drank from the cup of God's wrath, so that men wouldn't have to.
So now we come to the issue of who. All of humanity stood condemned. Jesus came and said "See that man over there, and that one too, and those over there ... I want them to be mine -- and I'm willing to pay." God granted Him His wish, allowed Him to pay the price (even though it meant subjecting His own beloved Son to torture and death, both at the lowly hands of created men, and at His own hand, as He crushed Him with the punishment for sin).
So if Jesus says "I paid for that one.", who are we to argue and say it isn't fair that He doesn't choose another? We do know several things about His choice:
- He doesn't base His choice on the good works or worthiness of individual people.
- He does not leave it up to men to find Him, but goes out and hunts down His lost sheep, however far out of the fold they might be.
- He does often extend His mercy and call through to descendants of ones He has already called and saved, but this is not a guarantee. Some that grew from the same branches are also pruned.
- It isn't the job of Christians to do the picking and choosing. In fact, quite the opposite: those who have been chosen are also commanded to go out and proclaim what Christ did to ALL: announcing to them that there is One who has taken away the sins of the world, and that through Him they might be saved.
There are quite a number of other points that could be made about your question. I'll address a few more in brief:
"those who are simply unable to believe in any god"
The Bible does not acknowledge the validity of atheism. On the contrary, it states that all men, whether they acknowledge it or not, have an innate knowledge of God. It also says that all of creation declares Him, albeit in a general way. Quite simply, this is not a valid excuse.
"Belief isn't a choice..."
After a fashion, I would actually agree with this, but not in the way you are thinking. I would say men did have a choice, and they choose wrong. And now you don't have the power to make a right choice. In that sense, without God's intervention, you cannot just up and decide to change your fate. One theologian humorously addresses this point this way:
Augustus Toplady: “A man’s free will cannot cure him even of the toothache, or a sore finger; and yet he madly thinks it is in its power to cure his soul.”
Adam was a prototype; you are of the same stock. You choose, and continue to choose, sin. Your own free will, left to its own ends, will never choose anything else. Yet Christianity calls men to make a new choice, to believe in Christ, to put their trust in Him, and stake their lives on the work that He did in removing our guilt from sin in the eyes of God. It also holds that this is only possible through a supernatural work --the intervention of the Holy Spirit-- in which God rips out your faithless heart of stone, and gives you a heart of flesh that is able to believe, love and obey -- but this, being His work, does not excuse you from searching out, wanting, and submitting to this new birth.
"the fair way would be for him to appear to every human at birth"
Who are you to say what is or isn't fair? What is a pot to say to the potter that "you should have made me with a handle"? There are some aspects of faith that are a mystery --that we don't have answers for-- but even human logic could present an argument about this scenario being 'fair'. If the outcome you expect is for everybody to be united under one unanimous belief, then whatever God must have done to make that happen would have destroyed any pretense of free-will they had. Would you have us all be robots? Is being a free-willed but fallen human who is then chosen to be resurrected from a living death and eventually restored to perfection in Glory not enough drama and beauty for you? Will you not bow in recognition that the Christ who did this is Lord -- and do so now willingly... before being left no other choice?
TL;DR: All of God's creation stands in rebellion of Him, and justly deserves to be destroyed. Only one Man was ever sinless, and that Man laid down His life so that others might live. How He picks who to adopt isn't the business of the newly adopted children. It is their job to turn around and tell others that He's still in the adoption business. If "fairness" is being stretched, it is being stretched in the direction of no-one deserves anything, so anything we get is all grace.