I've managed to answer a few of the latter questions, and please look below for a solution in the finite-degree case.
Theorem. There is an uncountable graph $\Gamma$ that is not a Cayley graph in the set-theoretic universe $V$, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing.
Proof. Let $\Gamma$ be a directed graph that is a tree, such that all vertices have infinite in-out degree, but such that some of these degrees are countable and some uncountable. For example, perhaps all the in-degrees are countable and all out-degrees are uncountable. It is not difficult to construct such a graph. Clearly, $\Gamma$ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by $V$, and perform forcing to a forcing extension $V[G]$ in which $\Gamma$ is countable. (It is a remarkable fact about forcing that any set at all can become countable in a forcing extension.) In the extension $V[G]$, the graph $\Gamma$ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, $\Gamma$ is the Cayley graph of the free group on countably many generators. $_\square$
Theorem. There is a graph $\Gamma$ which is not a Cayley graph, but every finite subgraph of $\Gamma$ is part of a Cayley graph. Indeed, every countable subgraph of $\Gamma$ is part of a Cayley graph. Every countable subgraph of $\Gamma$ can be extended to a larger countable subgraph of $\Gamma$ that is a Cayley graph.
Proof. The same graph $\Gamma$ as above works. Every countable subgraph of $\Gamma$ involves only countably many edges, and can be placed into a countable subgraph of $\Gamma$ that is the Cayley graph of the free group on countably many generators. $_\square$
The conclusion is that you cannot tell if an uncountable graph is a Cayley graph by looking only at the finite subgraphs, or indeed, by looking only at its countable subgraphs.
These observations show that in the uncountable case, one should just restrict the question at the outset to graphs satisfying the degree-matching condition.
Let me also give the fuller details for the finite-degree case, following the suggestion of François Dorais (and my tree-of-attempts argument).
Theorem. There is a finitistic condition on
countable graphs $\Gamma$ that holds exactly of the
finite-degree Cayley graphs. Specifically, the set of
finite-degree countable Cayley graphs has complexity at
most $\sum_4^0$ in the arithmetic hierarchy.
Proof. Let us suppose that the graph $\Gamma$ is given to us
simply as a binary relation on $\omega$, that is, an element
of $2^{\omega\times\omega}$. The assertion that the
graph is connected has complexity
$\prod_2^0$, since you must only say that
every two vertices are connected by a finite path. The
assertion that the graph has finite degree and all in-out
degrees are the same has complexity
$\sum_4^0$, since you can say "there
is a natural number $k$ such that for all vertices $v$ there
are $k$ vertices $w_1,\dotsc,w_k$ pointing at
$v$, such that no other vertex points at $v$ (and similarly for
pointing out).
Now, suppose that $\Gamma$ is a connected directed graph and
all in-out degrees are $k$. Fix a node $e$ that will represent
the group identity (if $\Gamma$ is a Cayley graph, any node
will do since they all look the same, so take $e=0$). Let us
refer to the $k$ nodes pointed at from $e$ as the set of
generators (since if $\Gamma$ really is a Cayley graph,
these will be the generators). Define that $p$ is a partial
labeling of the edges of $\Gamma$ with generators, if $p$ is
a function defined in a finite distance ball of $e$ in
$\Gamma$, where $p$ labels each arrow in that ball with a
generator. Such a labeling is coherent if first, for
every node every generator is used once going out from that
node and once going into that node, and second, if for
every node $v$, if there is a loop starting and ending at $v$,
then the word $w$ obtained from that loop works as a loop
from every node to itself. We only enforce the requirements on coherence of $p$ as far as $p$ is defined (since it is merely a partial function). Thus, a coherent labeling is an attempt to
make a labeling of the the graph into a Cayley graph, that
has not run into trouble yet.
Let $T$ be the collection of finite coherent labelings,
labeling all edges on the first $n$ nodes for some $n$. This is
a finitely branching tree under inclusion.
I claim that $\Gamma$ is a Cayley graph if and only if there
are arbitrarily such large coherent labelings. The forward
direction is clear, since we may restrict a full coherent
labeling to any finite subgraph. Conversely, if we can find
a coherent labeling for any finite subgraph of $\Gamma$,
then the tree $T$ is infinite and finitely branching. Thus,
by Konig's lemma there is an infinite branch. Such a branch
labels all the edges in $\Gamma$ and satisfies the coherence
condition. Such a labeling exactly provides a group
presentation with Cayley graph $\Gamma$.
The complexity of saying that every initial segment of the
nodes admits a coherent labeling is
$\prod_2^0$, since you must say for every
$n$, there is a labeling $p$ of the first $n$ nodes such that $p$
is coherent. Being coherent is a
$\Delta_0^0$ requirement on $p$. $_\square$
In particular, to recognize when a graph is a finitely
generated Cayley graph does not require one to quantify
over infinite objects, and so for finite degree graphs,
this is an answer to the main question.
I was surprised that the part of the description driving
the complexity is the assertion that the degrees must all
match, rather than the assertion that there are coherent
labelings on the finite subgraphs. Can this be simplified?
This still leaves the case of countably many generators
wide open. Also, this still doesn't answer the question
about having a computable graph $\Gamma$, which is a Cayley
graph, but which has no computable presentation. Such an
example would be very interesting. Even in the finite
degree case, as I mentioned in the question, the best the
argument above produces is a low branch.
The Schur multiplier $H^2(G;{\mathbb C}^\times) \cong H^3(G;{\mathbb Z})$ of a finite group is a product of its $p$-primary parts
$$H^3(G;{\mathbb Z}) = \oplus_{ p | |G|} H^3(G;{\mathbb Z}_{(p)})$$
as is seen using the transfer. The $p$-primary part $H^3(G;{\mathbb Z}_{(p)})$ depends only of the $p$-local structure in $G$ i.e., the Sylow $p$-subgroup $S$ and information about how the subgroups of $S$ become conjugate or "fused" in $G$. (This data is also called the $p$-fusion system of $G$.)
More precisely, the Cartan-Eilenberg stable elements formula says that
$$H^3(G;{\mathbb Z}_{(p)}) = \{ x \in H^3(S;{\mathbb Z}_{(p)})^{N_G(S)/C_G(S)} |res^S_V(x) \in H^3(V;{\mathbb Z}_{(p)})^{N_G(V)/C_G(V)}, V < S\}$$
One in fact only needs to check restriction to certain V above. E.g., if S is abelian the formula can be simplified to $H^3(G;{\mathbb Z}_{(p)}) = H^3(S;{\mathbb Z}_{(p)})^{N_G(S)/C_G(S)}$ by an old theorem of Swan. (The superscript means taking invariants.) See e.g. section 10 of my paper linked HERE for some references.
Note that the fact that one only need primes p where G has non-cyclic Sylow $p$-subgroup follows from this formula, since $H^3(C_n;{\mathbb Z}_{(p)}) = 0$.
However, as Geoff Robinson remarks, the group $H^3(S;{\mathbb Z}_{(p)})$ can itself get fairly large as the $p$-rank of $S$ grows. However, $p$-fusion tends to save the day. The heuristics is:
Simple groups have, by virtue of simplicity, complicated $p$-fusion, which by the above formula tends to make $H^3(G;{\mathbb Z}_{(p)})$ small.
i.e., it becomes harder and harder to become invariant (or "stable") in the stable elements formula the more $p$-fusion there is. E.g., consider $M_{22} < M_{23}$ of index 23: $M_{22}$ has Schur multiplier of order 12 (one of the large ones!). However, the additional 2- and 3-fusion in $M_{23}$ makes its Schur multiplier trivial. Likewise $A_6$ has Schur multiplier of order 6, as Geoff alluded to, but the extra 3-fusion in $S_6$ cuts it down to order 2.
OK, as Geoff and others remarked, it is probably going to be hard to get sharp estimates without the classification of finite simple groups. But $p$-fusion may give an idea why its not so crazy to expect that they are "fairly small" compared to what one would expect from just looking at $|G|$...
Best Answer
(Written before clarification at end of question was added). Here is a result which seems to be of a somewhat negative nature in the context of your problem, and your suggested line of attack, I think. I will denote the number of conjugacy classes of $G$ by $k(G)$. The group $ G = {\rm SL}(2,2^{n})$ (n>1) is a triply transitive permutation group on $1+2^{n}$ points and has order $(2^{n}+1)2^{n}(2^{n}-1)$. It has $1+2^{n}$ conjugacy classes, so that $k(G) > |G|^{\frac{1}{3}}$. Furthermore, the only orders of centralizers of non-identity elements of $G$ are $2^n$,$2^{n}-1$ and $2^{n}+1$. Hence the minimum centralizer order for an element of $G$ is only marginally smaller than $|G|^{\frac{1}{3}}.$ Admittedly this is a rather special group and a rather rare situation, but it is an infinite family of "bad" examples.
Added later: come to think of it, there are even bad solvable examples. If we take any prime power $p^{n}$ there is a doubly transitive solvable permutation group $G$ of order $p^{n}(p^{n}-1)$ and degree $p^{n}$(this is a Frobenius group which is the semidirect product of a vector space of size $p^n$ acted on by a Singer cycle of order $p^{n}-1$. A point stablizer is cyclic of order $p^n -1)$.` In this group, the only centralizer orders for non-identity elements are $p^n$ and $p^{n}-1$. Hence the minimum centralizer order for $G$ is not much less than $\sqrt{|G|}.$ So it seems that you can't expect to get much less than $\sqrt{|G|}$ for the smallest centralizer order for $G$. I suspect that even this would be very difficult to prove without the classification of finite simple groups.
Later remark: It is perhaps worth remarking explicitly here (though I am sure everybody knows it), that $S_n$ contains an element whose centralizer has order $n-1$ (and this is minimal), and that for $n > 4$, $A_n$ contains an element whose centralizer has order $n-2$, which is also minimal. Hence the "generic" highly transitive permutation group of degree $n$ behaves as hoped for large $n$ (and for sufficiently large $k$ there are no others, using the Schreir conjecture for $k >7$ or the disallowed Classification of finite simple groups for $k > 5$).