Omniscience is a key aspect of God in Christian theology. Without omniscience, God cannot be the allfair arbiter of justice, because no matter the crime, the question "What if there were more fair circumstances for him?" could always be legitimately raised.
It may surprise that despite the farreaching implications of unlimited knowledge, some unalterable truths can be gleaned.
I. Knowability Paradox
To quickly cut to the chase, omniscience, whether personal such as a being's knowledge or impersonal like data on a disk, is not only possible, but necessary. This is because knowledge does not involve selfreference: I don't need to know that I know something, I simply know it. This somewhat foreshadows a problem with the objection dealt with below, but it's important to note in establishing that omniscience is possible.
Essentially, because all knowable truth can by definition be known, then it follows that it has or can have a connection, whether merely logical (e.g. math equations) or actual (physics), with whatever it is that can know it or store it as information. If we posit that God is omnipotent, then all truth becomes knowable.
This idea is supported if not proven by "Fitch's paradox of knowability". From the Wiki:
Suppose p is a sentence that is an unknown truth; that is, the sentence p is true, but it is not known that p is true. In such a case, the sentence "the sentence p is an unknown truth" is true; and, if all truths are knowable, it should be possible to know that "p is an unknown truth". But this isn't possible, because as soon as we know "p is an unknown truth", we know that p is true, rendering p no longer an unknown truth, so the statement "p is an unknown truth" becomes a falsity. Hence, the statement "p is an unknown truth" cannot be both known and true at the same time. Therefore, if all truths are knowable, the set of "all truths" must not include any of the form "something is an unknown truth"; thus there must be no unknown truths, and thus all truths must be known.
In modal logic. Kp means "knowing a truth". LKp means "possible to know a truth". Givens:
(A) Kp → p knowledge implies truth.
(B) K(p & q) → (Kp & Kq) knowing a conjunction implies knowing each conjunct.
(C) p → LKp all truths are knowable.
(D) from ¬p, deduce ¬Lp 

if p can be proven false without assumptions, then p is impossible
(similar to the rule of necessitation: if p can be proven true without assumptions, then p is necessarily true). 
The proof proceeds:
 Suppose K(p & ¬Kp) I learn an unknown truth and now know it
 Kp & K¬Kp from line 1 by rule (B)
 Kp from line 2 by conjunction elimination
 K¬Kp from line 2 by conjunction elimination
 ¬Kp from line 4 by rule (A)
 ¬K(p & ¬Kp) from lines 3 and 5 by reductio ad absurdum, discharging assumption 1
 ¬LK(p & ¬Kp) from line 6 by rule (D)
 Suppose p & ¬Kp An unknown truth
 LK(p & ¬Kp) from line 8 by rule (C)
 ¬(p & ¬Kp) from lines 7 and 9 by reductio ad absurdum, discharging assumption 8.
 p → Kp from line 10 by a classical tautology
The last line states that if p is true then it is known. Since nothing else about p was assumed, it means that every truth is known.
Rule (C) is generally held to be at fault rather than any of the other logical principles employed. It may be contended that this rule does not faithfully translate the idea that all truths are knowable, and that rule (C) should not apply unrestrictedly. Kvanvig contends that this represents an illicit substitution into a modal context.
Gödel's Theorem proves that in any recursively axiomatized system sufficient to derive mathematics (e.g. Peano Arithmetic), there are statements which are undecidable. In that context, it is difficult to state that "all truths are knowable" since some potential truths are uncertain.
However, jettisoning the knowability thesis does not necessarily solve the paradox, since one can substitute a weaker version of the knowability thesis called (C').
(C') ∃p((p & ¬Kp) & LKp) & LK((p & ¬Kp) & LKp) There is an unknown, but knowable truth, and it is knowable that it is an unknown, but knowable truth.
The same argument shows that (C') results in contradiction, indicating that any knowable truth is either known, or it unknowable that it is an unknown yet knowable truth; conversely, it states that if a truth is unknown, then it is unknowable, or it is unknowable that it is knowable yet unknown.
(C') ∃p((p & ¬Kp) & LKp) & LK((p & ¬Kp) & LKp)
This is actually very simple. If the above is existentially true, then so is an instance of it:
9a. ((p & ¬Kp) & LKp) & LK((p & ¬Kp) & LKp)
10a. ((p & ¬Kp) & LKp) & LK(p & ¬Kp) & LK(LKp) Line 9a by Rule (B)
11a. LK(p & ¬Kp) Line 10a, conjunction elimination
And lines 1213 would be identical to lines 1011 above, concluding all knowable truths must be known instead of all truths must be known (making them all knowable): even though p represents simply a "truth" not a "knowable truth"  because (C') replaces (C) (or else we're just assuming (C) again). Line 11 can't be denied anyway, otherwise one is arguing it's impossible to ever learn any unknown truth. In fact, (C') can be reduced to: LK((p & ¬Kp) & LKp)  it's possible to know an unknown, but knowable truth.
Some object to the distributive property in (B), but versions of the paradox that don't use it exist. [Williamson, T. (1993). Verificationism and NonDistributive Knowledge, Australasian Journal of Philosophy, 71: 7886][Jago, M. (2010). Closure on Knowability, Analysis, 70: 648659.]
Additionally, if we try to probe the paradox for inaccuracies in the modal logic, developing line 6, which assumes the opposite of line 1 since that led to a contradiction, we get:
6. ¬K(p & ¬Kp)
7b. ¬Kp & ¬K(¬Kp) From line 6 by Rule (B)
8b. ¬K(¬Kp) From line 7b by conjunction elimination
But ¬K(¬Kp) does not equal Kp, or Line 7b can become ¬Kp & Kp. If I don't know that I don't know a truth, that doesn't mean I know it. It's like not knowing a question or its answer and concluding I know both; perhaps due to the intensional nature of knowledge. We can show this by adding a new rule: if I don't know a truth, it is still a truth!, so, adding this new rule: (E) ¬Kp → p . Substituting ¬Kp with p, I get:
9b. ¬K(¬Kp) → ¬Kp Not knowing that I don't know a truth means I don't know it
10b. ¬Kp & ¬Kp Line 7b by Rule (E)
11b. ¬Kp Line 10b, conjunction elimination
So unlike Line 1, Line 6 doesn't lead to a contradiction. If someone objects that, if I don't know a truth it may or may not be a truth, the result still holds. In that case, instead of (E) ¬Kp → p , we have (E') ¬Kp → p v ¬p (not knowing p makes it a truth or untruth):
9c. ¬K(¬Kp) → ¬Kp v ¬¬Kp Substituting ¬Kp for p in Rule (E')
10c. ¬Kp & (¬Kp v ¬¬Kp) Lines 7b and 9c by Rule (E')
11c. ¬Kp & (¬Kp v Kp) Line 10c Double negation elimination
12c. (¬Kp & ¬Kp) v (¬Kp & Kp) Line 11c Associative Property
13c. ¬Kp & ¬Kp
Line 12c elimination of contradiction
14c. ¬Kp
Line 13c conjunction elimination
Again, no contradiction in itself nor with the conclusion from rule (E), showing the negation of Line 1 in Line 6 is valid. Also, one cannot assume ¬Kp → ¬p, which would lead to a contradiction, if one cannot assume ¬Kp → p. And since one can't assume both, ¬Kp → p v ~p.
That ¬K(¬Kp) → ¬Kp is confirmed by Line 7b, and this must be the case, otherwise both Lines 1 and 6 (from the original) lead to a contradiction, meaning an unknown truth/statement is neither known nor unknown, which is illogical. Moreover, the conclusion in Line 7 is that it's impossible to learn a truth, which is perhaps even more preposterous than all truths being known. In fact, one can simply skip to Line 9, but the problem is that if it's possible to know a truth and know that I don't know it, Line 9, if simplified simply becomes:
9d. LK(p & ¬Kp)
10d. K(p& ¬Kp)  Line 9d, if it's existentially true, then so is an instance
11d. Kp & K¬Kp  Distribution by Rule (B)
12d. Kp & ¬Kp  To know I don't know = I don't know; Contradiction
It can be shown that (E'') ¬Kp → ¬p is invalid because:
9e. ¬K(¬Kp) → ¬(¬Kp) substituting truth ¬Kp for p
10e. ¬Kp & (¬¬Kp) Line 7b and 9e by Rule (E'')
11e. ¬Kp & Kp Contradiction
I.1. Interpretation
Fitch's Knowability Paradox does not conclude that all knowable truths must be known the way we understand knowledge, but that if a truth is in actual fact knowable, by a human, computer, or donkey, then it will be known, or rather should eventually be known, or else it is unknowable. The paradox reflects reality since truth is irrespective of time and space  perhaps an interesting exploration in causality. It deals with certainties and results, not contingents and possibilities that may be possible but will never happen (counterfactuals). Hence, a genuinely stochastic system such as the path of particles is consistent since the paradox doesn't tell you which truths must be knowable.
So if I don't know something right this moment, then so far as the electricity in my brain is concerned, it is unknowable: if some outside electricity (five senses converted into electricity) adds/modifies the electricity in my brain, then we have contradicted ourselves earlier, and the electricity in my brain was not all of it, and the one outside my head that travelled to it now was previously always a part of it, so I always "knew" what my actual brain didn't. In other words, if I'm in a dark room and don't know the color of a ball there, when I turn on the light may be when my brain knows its color, let's say blue. But since the ball was always blue, the switch would always be turned on in this potential future (not that the future is set in stone, but the Paradox looks at reality, not possibility), and the light would always travel to the ball and bounce to my eye, then in that sense, the knowledge within that room was always there.
In that sense, perhaps the idea that some truths are unknowable isn't necessary, which is the idea most including Fitch derive from the paradox. If anything, pantheists would have a field day with this one.
This interpretation is confirmed by Line 7 which derives from Line 6 by Rule D. Since Rule D posits that a nontruth (¬p) cannot possibly be a truth ever (¬Lp), then the statement: "I don't know unknown truth p (Line 6)" itself being a truth, means it cannot be possible that "I know [this same] unknown truth p (Line 7)"  this is true if there is no time involved, which is either a flaw in the modal logic (below) or the interpretation above.
I.2. Semantic/Conceptual Objections
The main culprit is Line 1, namely K(p & ¬Kp). Since p & ¬Kp is "an unknown truth", how can K(p & ¬Kp), a "known unknown truth" be logical? Does an unkicked ball become both kicked and unkicked the moment it's kicked? (replacing Kp with Kicked(ball), Kick(b), derives the same: all kickable balls have been kicked). Yet, how does one learn an unknown? Where is the bridge between known and unknown, and how does it intersect? If they don't ever meet, what's inbetween; how can something be neither known nor unknown? (similar to questions for discrete space  what's in between points of space?)
This may potentially relate to "This statement is false", whether because of the above "known and unknown" dilemma, or because of a potential semantic flaw. It may possibly disprove the idea that it's both true and false, since it leads to a contradiction: the fact that at some point a knowable but unknown fact must become both known and unknown at the same time.
Two counterarguments I can think of can arise. First, Schrödinger's Cat is both dead and alive. Second, Cantor's Set Theory exactly eliminates issues rooted in the bias of countabilty. Here's the fun of it, though: whether these or any other suggestion allows it, either way Line 1 either cannot be true, or leads to a contradiction: meaning it cannot be true. However, it would be worth exploring for the other issue(s) mentioned above.
As noted, the problem is that to learn a truth, at some point one must both know and not know it. This may be possible if we apply Cantor's solution to Zeno's Paradox and consider the shift to be at an uncountable point, similarly to how 0.999...=1, and the smallest shift to the next number, literally a dot (which has 0 dimensions), both exists and doesn't exist in the same way. The same issue exists with the contradiction derived in Line 6 (because of the same phenomenon we see in Lines 12). Additionally, in Line 7 we see a possible deficiency in the modal logic because, while rule D can be expressed another way to allow Line 7's validity (all truths are necessarily true; all necessarily nontruths are not possible truths [¬p → ¬Lp; plugging Line 6 as p gives us Line 7]), it presumes no time (supporting the interpretation above, but also begging the question and throwing doubt on the whole Paradox). Because if it's true that I don't know something and don't know that I don't know it (Line 6), then Line 7 tells us it's not possible to apparently ever know it, hence making Line 11 a foregone conclusion due to this absence of time.
II. Halting Problem
Discovered by Alan Turing, the Halting Problem is essentially an issue in computation when the machine/computator is a part of the computation. For example, a scale can't weigh itself. A dictionary can never completely define every word because it uses those same words to define others.
Imagine a psychic who knows the future perfectly  100%, never wrong. Everyone flocks to her to know their future. But she becomes burdened due to this demand. She builds a machine that reads her mind and gives people their answer without needing her presence. This answer is from her, so it's still 100% accurate, knowing the future. Now imagine the psychic goes to this machine and asks the machine, "What will be my next word?" What would the machine say?
The machine will actually stall and never say anything. Even if the psychic had no free will and were a robot, completely predetermined, it would not be able to say anything! This is because the psychic/robot is asking the machine, which is asking the psychic, which is asking the machine, which is asking...
Now replace the psychic with God. Can God know His next word/action before He makes it? The answer is the same: No. This is not because God is not omniscient or because omniscience doesn't exist, any more than truth not existing. It's simply an illogical situation and our conceptual bias fools us into thinking it's knowledge and lack of knowledge to not "know" (do you "know that you know that you know..." or do you just "know"?). To conclude this would be the same as saying a scale weighs nothing since it can't weigh itself. And that's not an argument of omnipotence either because it's pitting the scale's power against itself.
III. Objections to Omniscience
III.1. Berg's Objection
In his The Six Ways of Atheism, Geoffrey Berg attempts to oneup Aquinas' "Five Ways" or proofs of God with six proofs against his existence. His first four are statistical and definitional nonsense arguments ("many religions" "give me a definition of God", "God and man's knowledge is too wide", etc). His last is an even more absurd, weird "no purpose to life" argument. It's his fifth that actually deserves merit.
Berg essentially states that no matter how much knowledge a being has, this being can never know that it knows everything; that there is nothing more to know. Because to know that you know everything, you have to verify by going outside the totality of knowledge to know there isn't more to know, which is a contradiction.
This is in a sense similar to Gödel's Incompleteness Theorems because the statement 1+1=2 can only be proven if one assumes that 1=1 or more generally, x=x. And if you try to prove that, you will simply run into more axioms to prove. Interestingly enough, David Hilbert, whose program in 1900 launched an attempt to "complete" mathematics and physics into a big, complete, selfconsistent collection of theorems and proofs was completely frustrated by this. Hilbert lived another 10 years after Gödel's proofs, and he seems to have dealt with the problem by something like an infinite chain of proofs, where basically each new axiom continually gets proven over and over in an attempt to suggest that it's the same as a single proof or collection of theorems, only the process is infinite. Just like some interpretations of the Knowability Paradox, it shows that not all truths can be verified if one rejects the claim that all knowable truths are known.
This approach is not exactly a sinking man's last plank, because it's exactly how irrationals function: an infinite series of numbers that somehow does transition. But unlike Set Theory there, these are countable proofs and Gödel's proofs are final: one third equals 0.3333... to infinity even though eventually after an uncountable number of "three's", it all becomes a "one" when multiplied by 3. And the approach is neither practical, nor really necessary: why do I need to prove that 1=1 anyway, if I realize I can't?
However, the same idea could be employed to Berg's objection, perhaps with a little more luck. Essentially, let's suppose that my knowledge K is the complete set of all truths. In this set, p is a truth and I know it; that is, element p is in set K. In that case, I don't need to discover that ~p (the opposite of p) is untrue because I already know this by knowing the truth of p.
However, the problem is that in order for it to be true that K, my whole set of knowledge, contains ALL knowledge, then I must know that K & x is untrue, where x is some proposition not found in K. If I make K & x a part of K, then the question simply becomes, "What about (K & x) & y?" Essentially, an omniscient being has to know what it doesn't know in order to know it's omniscient (or omnipotent actually), and this is impossible because for every verification there is another one necessary. If one supposes an infinite such checks, we run into the problem Hilbert had mentioned above. One can exhaust an infinite amount of possibilities by a formula. For example, x=x denies 1=2, 1=3, 1=4, all the way to 1=any infinite number. But the very problem is that to accomplish this, one needs to know that x=x. It's the same principle with physical reality: how can one know there isn't another universe if one is unable to measure it? How can an omnipotent being know it's omnipotent or unchangeably limited?
Yet the problem with Berg's objection lies in the presumption that these verifications are truths, when in fact they are logical impossibilities. It's a little like asking by what power any force exists: e.g. "What pulls gravity to make it pull?" Knowledge simply exists in the same way as power, because knowledge is based on existence and fundamentally is the power of anything to exist. A computer's data can't exist without the electrons and is in fact identical to those electrons. This is exactly why the Knowability Paradox concludes that all knowable truths must be known: it isn't accounting for time and space barriers, but the definition of "knowable" with respect to truth, which should be timeless and "spaceless" (i.e. it's not any less true in a different part of the universe), means that it is already known or else there is some barrier. Since time and space are not accounted for, one is only looking at the end result at all times: a conclusion identical to the fact that the ends don't justify the means. This is also how God can accept sinners who would have both sinned and not sinned if having been made angels, but be sinless.
This isn't because of a deficiency in the definitions or modal logic above. Simply put, imagine there's an object behind a curtain. You can't see it and you don't know it. Once the curtain pulls away you know it. It's a knowable but unknown (prior to the curtain pulling) for you truth. But is there any distinction between the electricity in your brain that comprises your knowledge and the light that bounces off the object and hits your eyes? If there is, why? What's the difference? At what point does the electricity/knowledge become your electricity/knowledge? If we restrict your knowledge to electricity within your brain only between specific points (say between neurons), then it's true that you don't know the object and will never know it from that electrical information  until the light arrives from outside, but that isn't part of you and your electrical composition including the momentum and direction of the electrons. In that sense, you're nonomnipotent, but with respect to God, He does not have this shortcoming.
It's this very issue that the Knowability Paradox addresses by saying that there never was any distinction and you always "knew" what the object was. The only difference between a knowable and unknowable truth in that sense becomes the questions: can I and will know it? Because possibility without actuality is equivalent to impossibility with respect to knowledge. If I can show my art to someone but never do, then I never could have shown them my art in this fatalistic sense in which truth necessarily lives. Perhaps it's human language or concept, but it's a confusion between counterfactuals and reality, showing in fact that counterfactuals do not exist in reality, even if they are valid and could have. This also shows that God's will would be immutable and He couldn't know it before deciding it.
For the same reason that facts exist, yet Gödel's Incompleteness Theorems are, well, theorems, Berg's objection falls apart. The argument becomes similar to the "Can God make a rock so heavy not even He can lift?" dilemma. It would seem from the Knowability Paradox that omnipotence not only allows but entails omniscience?
If the Paradox is valid, especially if the interpretation in Section I.1 above is correct, then Berg's objection collapses because it means one does not need to verify knowledge to have it (to know one knows everything); one simply has to have it, like knowing your phone number. Ultimately, even without the Knowability Paradox, Berg's objection is flawed. If the information exists, by definition it can be known (otherwise one would not be omnipotent if unable to reach it). If it's unknowable, then it's not information. Gödel's Theorems support that some truths are unknowable at a certain point, and in that sense they don't become truths until later: for example, if the psychic hasn't said a word in the example above, the words she does say later become that truth, but it is not true prior to uttering them. In a sense this argues that all truths are knowable. But since we're assuming omnipotence, then either reality can actuate these truths (i.e. they can exist), which means God can have access to them if He exists and is more powerful than the universe, or they don't exist or are logically unobtainable, which means one is no longer talking about omniscience if it's not logical to know.
I believe omniscience is misused as an entity. Knowledge is based upon information which doesn't exist outside of physical contact (e.g. a computer has no data without electrons and their pattern). Since infinite sets can contain themselves in themselves (e.g. the set of all sets contains itself as well as the set of all primes, etc), the proof of something (and an infinite chain of it) can be within the infinite set of known facts anyway: this by itself would also be proof of a being's omnipotence since it otherwise wouldn't be able to store an uncountable number of infinite facts. But that's verification, which it wouldn't need, so the real question is how does a being know it's omnipotent without needing to test its powes? Anyway, since knowledge doesn't exist outside of existence, to ask proof of knowledge is like asking "how is reality real?"  does truth need to prove itself as true for reality to contain it as truth?
A nonomniscient, omnipotent being can actually become omniscient by accessing/creating all possible spaces and observing them, and this would not be a simulation because of the highest cardinality (unlimited number of cardinalities in set theory) it would be capable of accessing to create or not create. This occurs in nature all the time anyway (e.g. action at a distance: for example, magnets do not interact physically with magnetic metals yet somehow "know" which are magnetic).
Since it's illogical to know a falsehood, knowing that I know is the same thing as "I know":
Let p mean "truth", Kp represent "Knowing a truth"; ¬Kp is "not knowing a truth" and ¬p = a falsehood
1. Kp → p


Knowledge implies truth

2. Kp → ¬K¬p


Knowing a truth means you don't accept falsehoods as knowledge  different from knowing a falsehood which is still a truth statement (e.g. I know 2+2=5 is false vs I "know" 2+2=5)  this can be proven, because if I assume:


2b. Kp → K¬p



3b. ¬Kp v K¬p


I either don't know a truth or know its falsehood. Meaning if I know something true then I either don't know it or I only know its false opposite: a contradiction. 

So:
1. Kp → p



2. Kp → ¬K¬p



3. ¬Kp v ¬K¬p


De Morgan on Line 2

4. ¬K¬p


Since ¬Kp is false

Knowing a truth means one does not know that truth's falsehood (not a lack of knowledge, but something illogical to know). Hence knowing all truths means one doesn't have to know (or explore) falsehoods like "there is another truth you don't know". Proof is different from knowledge/truth as Gödel's Incompleteness Theorems show.
If one still isn't convinced of this, then a simple way God could verify not only his omniscience but omnipotence would be if He observed/created all possible spaces in n=infinite dimensions. This would allow Him to know that He knows all truths in synthetic reality (e.g. the universe or other dimensions). If one objects that verification implies uncertainty which contradicts omniscience, then one has to prove that knowledge necessitates verification by physical, local contact (e.g. I don't know the color of a boat until I look at it), whereas accurate information can come from nothing/noncontact (e.g. virtual particles in quantum fluctuations that come from zero energy yet "know" the laws of physics and obey them). One would not need to disturb what one observes because as we show information can come from nothing (e.g. the universe's own existence), and above we see it can be accurately duplicated.
IV. Peripheral Issues
IV.1. The Knowability Paradox and the Incarnation
Strangely and interestingly, Jonathan Kvanvig contends that the Knowability Paradox contradicts the doctrine of the Incarnation of Jesus. [Kvanvig, Jonathan. The Incarnation and the Knowability Paradox. Synthese 173, no. 1 (2010): 89105. (JSTOR link)] Once again, this sees the Knowability Paradox where knowledge is measured by neurons, or maybe computer data, a view not shared above. His idea is that God can Incarnate Himself as a human and be omniscient, which means that it's possible for a human, any human, to be omniscient. Since any human could possibly be/become omniscient (perhaps God gives him all His knowledge, making it physically possible to obtain and retain it with physical "enhancements", being omnipotent (p.11)), then all facts are possibly known truths for every human. As we saw above, all knowable truths must be known, so Kvanvig concludes that the Knowability Paradox either means that all humans are omniscient or that there are unknowable truths, meaning omniscience cannot exist.
Since Kvanvig uses the traditional Knowability Paradox, where (C) says that all truths are knowable, the option that there are unknown truths is on the table, which he accurately says must be rejected by traditional theists/Christians. However, with the weaker version, where (C') is all knowable truths can be known, this option disappears anyway, so we're left with the same problem that Kvanvig states.
If God can make an omniscient human, he can make an omniscient computer, or animal, or anything. And the fact that the weaker version of the Paradox is still valid shows that the interpretation by Kvanvig (and intuitively by most) is inaccurate.
V. Resources