How is Gods judgement of man fair when he judges them without considering their deeds? In America, our judicial system is built on the idea that a man is assumed innocent, and then proven guilty with evidence.

In contrast, Paul wrote:


  Romans 9 10-18: ...there was Rebekah also, when she had conceived twins by one man,
  our father Isaac; 11 for though the twins were not yet born and had not
  done anything good or bad, so that God’s purpose according to His
  choice would stand, not because of works but because of Him who calls,
  12 it was said to her, “THE OLDER WILL SERVE THE YOUNGER.” 13 Just as it
  is written, “JACOB I LOVED, BUT ESAU I HATED.”
  
  14 What shall we say then? There is no injustice with God, is there? May it never be! 15 For He says to Moses, “I WILL HAVE MERCY ON
  WHOM I HAVE MERCY, AND I WILL HAVE COMPASSION ON WHOM I HAVE
  COMPASSION.” 16 So then it does not depend on the man who wills or the
  man who runs, but on God who has mercy. 17 For the Scripture says to
  Pharaoh, “FOR THIS VERY PURPOSE I RAISED YOU UP, TO DEMONSTRATE MY
  POWER IN YOU, AND THAT MY NAME MIGHT BE PROCLAIMED THROUGHOUT THE
  WHOLE EARTH.” 18 So then He has mercy on whom He desires, and He
  hardens whom He desires.


One way to defend the christian God here is to say Paul is just speaking of Jacob and Esaus relative stations in earthly life, and that only that aspect of their lives was predetermined. But that idea is invalid with regard to verses 14-18 which connect Jacob and Esau's example to Pharaohs, in which Pharaoh's damnation was predetermined. Also, the declaration "I will have mercy on whom I have mercy" contradicts that idea. It is clear then, from these verses, that Paul is boasting that God judges people based on his whim, not a trial.

Another way to defend the christian God, which I've heard, is "God doesn't have to sound fair by human reasoning." But human reasoning is all we have, to use to make decisions about what we believe. Also what's fair or not is known by everyone by instinct. We all know judgement cannot happen without considering some action which is being judged. Not requiring Gods judgement to be just according to us is forgoing any understanding of God.
Comparing the representative democracy of America with the kingdom of God is an unparalleled category error.  The entire reason American jurisprudence holds a person innocent until proven guilty is because we assume that we are not privy, at the outset, to all of the pertinent facts.  You may accept this or not but the Scripture declares that God knows the end from the beginning.  God is not awaiting the disclosure of temporal evidence in order to render righteous judgement.

Regarding the specific passages that OP has pointed to, there's a lot going on here that needs to be weighed into the discussion.  Primarily, the entire context of chapters 9-11 of Romans has to do with God's sovereign choice of a nation; an entire people group, therefore it is somewhat out of context to reduce what is being said merely to God's judgement of an individual.  


  I am speaking the truth in Christ—I am not lying; my conscience bears me witness in the Holy Spirit— that I have great sorrow and unceasing anguish in my heart. For I could wish that I myself were accursed and cut off from Christ for the sake of my brothers, my kinsmen according to the flesh. They are Israelites, and to them belong the adoption, the glory, the covenants, the giving of the law, the worship, and the promises. To them belong the patriarchs, and from their race, according to the flesh, is the Christ, who is God over all, blessed forever. Amen. - Romans 9:1-5


Even though individual names are mentioned in the passage it is very common for names to represent entire nations.  Israel, in fact, is what Jacob's name was changed to and the Scriptures are replete with examples of the entire nation being referred to by both names.  The same is true of Esau.  The exact passage from Genesis that Paul refers to in this text is very clear that this is exactly what is going on:  


  And the LORD said to her, “Two nations are in your womb, and two peoples from within you shall be divided; the one shall be stronger than the other, the older shall serve the younger.” - Genesis 25:23


It is critical, then, to keep a tight grip on this context as one investigates what Paul is saying.  It is clear in Scripture that God did not select Israel to be His chosen people because of any intrinsic quality that they had.


  It was not because you were more in number than any other people that the LORD set his love on you and chose you, for you were the fewest of all peoples, but it is because the LORD loves you and is keeping the oath that he swore to your fathers, that the LORD has brought you out with a mighty hand and redeemed you from the house of slavery, from the hand of Pharaoh king of Egypt.  - Deuteronomy 7:7


In fact, it is also clear in Scripture that God's mercy is continually extended towards His people despite their behavior


  “For I the LORD do not change; therefore you, O children of Jacob, are not consumed. From the days of your fathers you have turned aside from my statutes and have not kept them. Return to me, and I will return to you, says the LORD of hosts. - Malachi 3:6-7


Secondly, it is noteworthy that the passages quoted by the OP have much to do with sovereign choice and mercy.  There is no mention of judgement in the strictest sense.  What we see is Paul asking a rhetorical question about whether it is unjust of God to sovereignly dispense mercy and compassion.  The implication that the flip side (judgement or condemnation) are also in view is not faulty because mercy is always, only given where condemnation is due; mercy is undeserved.  Paul's point is that, where perfect justice is represented (remember that Paul has already demonstrated that the whole world is guilty before God), it is not unjust for God to show mercy wherever He will.  However, it is faulty to assume that God's withholding of mercy is unfair or unfounded.  Mercy deserved is no mercy at all, it is payment.

This is why Paul brings Pharaoh into the conversation.  Pharaoh is named as the representative head of Egypt, which nation was raised up by God in order to rescue His people from famine and strengthen them in number and to enslave that same people so that God could demonstrate His power and favor toward Israel in delivering them in miraculous fashion from the power of Pharaoh (Egypt).  God hardened Pharaoh's heart and Pharaoh also hardened his own heart but the salient point is that Pharaoh and indeed all of Egypt were wicked and idolatrous.  To suppose that God's hardening of Pharaoh's heart, as regarding the release of the enslaved Israelites, was unjust is to completely disregard the baseline condition of enmity towards God which characterized Pharaoh's heart to begin with. 

Finally, assuming that a finite, created being can ever comprehend justice on a Divine, omniscient scale and thus rightly use that scale to accurately measure the infinite Creator is the highest hubris.  A dog can put it's head out the window and enjoy a car ride but it will never understand the internal combustion engine nor critique it's design or operation.


  But who are you, O man, to answer back to God? Will what is molded say to its molder, “Why have you made me like this?” Has the potter no right over the clay, to make out of the same lump one vessel for honorable use and another for dishonorable use? - Romans 9:20-21


Two different vessels made of the same lump of clay.  The vessels have different uses as the Potter sees fit but the formative lump is the same ruined, sinful clay.  The giving or withholding of mercy has nothing to do with justice.