For infinite sets, $A$ having larger cardinality than $B$ already implies that $A$ is "much larger," and perhaps a good way to see this is to think of all the ways of making $B$ "larger" which don't increase its cardinality. E.g. taking the union with any set of equal or smaller cardinality, taking the Cartesian product with a set of equal or smaller cardinality, etc.
Perhaps you want to know if there are a lot of other cardinalities in between those of $B$ and $2^B$. This question can't be answered with the usual axioms of set theory. For more information, read about the generalized continuum hypothesis.
Edit: In your extended question, you mention that the usual argument only guarantees that the power set $2^A$ has "one more" element than the original set $A$: given a map $\phi : A \to 2^A$, there is at least one element not in the image of $\phi$. Call that element $x$. Certainly there is a bijection between $A$ and $A \cup \{x\}$, so repeating your argument shows there isn't a bijection between $A \cup \{x\}$ and $2^A$; at least one element is missed. So in fact $2^A$ has "two more" elements than $A$. Repeating this, one sees there are infinitely many elements missed. Moreover, by showing that $A \times A$ cannot be mapped onto $2^A$, there are at least "$|A|$ more" elements in $2^A$, and so on.
This is what I was trying to get at in my first paragraph. Of course, it has to be understood in the context that adding one element to an infinite set doesn't actually make it any larger in the sense of cardinality. To my mind, cardinality is a very crude measure of the "size" of an infinite set, and so any operation that enlarges it to an extent that it can be detected by cardinality must be a very dramatic enlargement indeed.
The answer is no. Let ZC' be ZFC without replacement and infinity and with the assertion there is a Kuratowski infinite set. We will construct a model $M$ of ZC' such that only hereditarily finite elements of $M$ are fixed under all automorphisms of $M.$ The idea is generate a model from a $\mathbb{Z}^2$-array of objects, each of whose only element is the object below it in the array.
Define $M=\bigcup_{m<\omega} \bigcup_{n \in \mathbb{Z}} \mathcal{P}^m(\{\omega\} \times \mathbb{Z} \times [n, \infty)),$ where we adjust the $\mathcal{P}$ operator to replace each singleton of the form $\{(\omega, n_1, n_2)\}$ with $(\omega, n_1, n_2+1).$ (We use $\omega$ to differentiate the $\mathbb{Z}^2$ objects from the hereditarily finite sets).
Define a relation $E$ on $M$ by $E \restriction \mathbb{Z}^2=\{((\omega, n_1, n_2),(\omega, n_1, n_2+1)): n_1, n_2 \in \mathbb{Z}\}.$ Extending $E$ to the iterated power sets is done in the natural way. It is easy to see $(M, E)$ satisfies ZC'.
Notice that the map $(\omega, n_1, n_2) \mapsto (\omega, n_1, n_2+1)$ extends to a unique automorphism on $M,$ which only fixes hereditarily finite elements. Thus, none of the infinite sets in the model are first-order definable.
Update: The author of this question was curious whether there is such a model which also satisfies transitive containment (TC), the assertion that every set has a transitive closure. The answer is yes; here's a sketch of such a model.
Assume ZFC + "there are non-OD reals" in $V$ (or work in a ctm satisfying a sufficiently large finite fragment of this theory). We'll build an OD model $M$ of ZC'+TC such that, from every infinite element $x,$ we can define (in $V$) a non-OD real $r.$ Then $x$ is not definable in $M,$ or else we would have an ordinal definition for $r.$
For $r \in \mathbb{R} = \mathcal{P}(\omega),$ we recursively define $n_r$ by $0_r=\emptyset$ and $(n+1)_r =\{n_r\}$ if $n \not \in r,$ and $(n+1)_r = \{n_r, \emptyset\}$ if $n \in r.$ Basically, we're defining a new system of natural numbers for each real.
Let $M = \bigcup_{m=0}^{\infty} \bigcup_{S \in [\mathbb{R} \setminus OD]^{<\omega}} \mathcal{P}^m ( \{n_r: n<\omega, r \in S\} ).$
For each infinite $x,$ there are finitely many (and at least one) non-OD reals $r$ such that the transitive closure of $x$ contains every $n_r.$ The least such real is as desired. And it's routine to verify $M \models ZC'+TC.$
Best Answer
Yes. By Hartogs' theorem, there is an ordinal that has no injection into $R$. The minimal such ordinal is the smallest well-ordered cardinal not injecting into $R$. It is naturally well-ordered by the usual order on ordinals. None of this needs AC.
One can think very concretely about the order as follows: Consider all subsets of $R$ that are well-orderable. By the Axiom of Replacement, each well-order is isomorphic to a unique ordinal. Let $\kappa$ be the set of all ordinals that inject into $R$ in this way. One can show that $\kappa$ itself does not inject into $R$, and this is the Hartogs number for the reals.
More generally, of course, there is no end to the ordinals, and they are all canonically well-ordered, without any need for AC.
But in terms of the remarks in your "motivation" paragraph, there are linear orders that do not map order-preservingly into $R$ that are not larger than $R$ in cardinality. For example, the ordinal $\omega_1$ cannot map order-preservingly into $R$, since if it did so, then there would be an uncountable family of disjoint intervals (the spaces between the successive ordinals below $\omega_1$), but every such family is countable by considering that the rationals numbers are dense. Another way to see this is to observe that the real line has countable cofinality for every cut, but $\omega_1$ has uncountable cofinality.
Lastly, there is a subtle issue about your request that the order by "larger than $R$". The examples I give above via Hartog's theorem are not technically "larger than $R$", although they are not less than $R$ in size. The difficulty is that without AC, the cardinals are not linearly ordered, and so these two concepts are not the same. But you can turn the Hartogs argument into a strict example of what you requested by using the lexical order on $R\times\kappa$, where $\kappa$ is the Hartog number of $R$. This order is strictly larger than $R$ in size, and it is canonically linearly ordered by the lexical order.