There is no need to use the axiom of choice here. Suppose $X$ is an infinite well-orderable set. We argue that there is a well-ordered set $(Y,<)$ with $Y$ of strictly larger cardinality than $X$.
For this, consider the set $A$ of all binary relations $R\subseteq X\times X$ such that $R$ is a well-ordering of a subset of $X$. Let's call $X_R$ this unique subset.
We introduce an equivalence relation on $A$ by setting that $R_1\sim R_2$ iff $(X_{R_1},R_1)$ and $(X_{R_2},R_2)$ are order isomorphic. Let $Y$ be the set of equivalence classes.
We can well-order $Y$ by saying that $[R_1]<[R_2]$ iff there is an order isomorphism from $(X_{R_1},R_1)$ to a proper initial segment of $(X_{R_2},R_2)$. One easily verifies that $<$ is well-defined. This means that if $R_1\sim R_3$ and $R_2\sim R_4$, then $(X_{R_1},R_1)$ is isomorphic to a proper initial segment of $(X_{R_2},R_2)$ iff $(X_{R_3},R_3)$ is isomorphic to a proper initial segment of $(X_{R_4},R_4)$. One also verifies easily that $<$ is a well-ordering.
Finally, $Y$ has size strictly larger than $X$. To see this, note first that $X$ injects naturally into $Y$, namely, given a well-ordering $\prec$ of $X$ and any two initial segments $X_1$ and $X_2$ of $X$ under $\prec$, with $X_1$ a proper initial segment of $X_2$, $[\prec\upharpoonright X_1]<[\prec\upharpoonright X_2]$. But each point of $X$ determines an initial segment of $X$.
Now, if there were an injection $f$ of $Y$ into $X$, then the range $Z$ of $f$ would be well-orderable in a way isomorphic to $(Y,<)$ by using $f$ to copy the well-ordering $<$ of $Y$: Simply set $f(a) R f(b)$ iff $a<b$ for any classes $a,b\in Y$. We then have a copy of $(Y,<)$ as a proper initial segment of $(Y,<)$ (again, looking at initial segments of $(Z,R)$), contradicting that $<$ is a well-ordering.
The above may seem complicated but it is simple: All it is saying is that a well-ordering is less than another if it is an initial segment, and this is a "well-ordering of well-orderings". (And we have to use equivalence classes because different well-orderings may actually be isomorphic.)
When $X$ is a countably infinite set, the resulting set $Y$ is well-ordered and uncountable, but any initial segment of $Y$ corresponds to a well-ordering of $X$, so it is countable. If you want a set $B$ as required, simply set $B=Y\cup\{*\}$ where $*$ is some point not in $Y$, ordered by simply making $*$ larger than all the elements of $Y$. Then $\{a\in B\mid a<*\}$ is uncountable, but $\{c\in B\mid c<d\}$ is countable for any $d\in Y$, i.e., for any $d\in B$ with $d\ne *$.
Once you are familiar with the construction of ordinals, the above can be streamlined a bit: Rather than using an equivalence class, we simply use the ordinal isomorphic to any representative of the class. The argument above gives us that the collection of countable ordinals is actually a set, and its union is an (in fact, the first) uncountable ordinal. As a matter of fact, there is not even the need to take a union. The set of countable ordinals is already an uncountable ordinal.
(The argument above shows that given any well-ordered set there is a larger well-ordered set. A similar argument gives that if we have a family of well-orders, we can paste them together to get a well-ordering larger than all the ones in the family.)
Suppose you are given an uncountable, well-ordered set $S$.
Isn't it possible to provide a bijection $f:\mathbb{N} \rightarrow S$
No. $\mathbb N$ is countable. You will end up with a set of elements $\{s_1,s_2,s_3,\dots\}$, but there will exist elements you have not covered. There is nothing in your definition that demands you covered all of the elements.
An example (not a well ordered set, I know, but may still illustrate my point) is if you look at the set $$S=\left\{\frac12, \frac23, \frac34, \dots, \frac{n}{n+1},\dots\right\}\cup[1,2]$$
The procedure you described works on $S$, although $S$ is not well ordered. It takes $\frac12 = s_1$ as it is the least element. Then it takes $s_2=\frac23$ and so on. It produces $s_i = \frac{i}{i+1}$ which is an injection from $\mathbb N$ to $S$, but it does not cover the whole $S$.
Edit: In fact, you can even take the set $$T=\left\{\frac12, \frac23, \frac34, \dots, \frac{n}{n+1},\dots\right\}\cup\{1\},$$
whic is well ordered and is even countable, but your procedure still does not produce a bijection from $\mathbb N$ to $T$.
Best Answer
For an uncountable well-order $(X,<)$ and define $C= \{x \in X\mid \{y \in X\mid y < x\} \text{ uncountable }\}$. If this set happens to be empty then $X$ itself is as required. If not, let $c_0 = \min C \in X$ which exists as $(X,<)$ is a well-order and let $Y = \{x \in C\mid x < c_0\}$ in the inherited order and $Y$ is then clearly as required, by minimality of $c_0$.