Consider the monoid of one-to-one functions from the set $\mathbb N$ of natural numbers into (not necessarily onto) itself. The monoid operation is composition, and my notational convention is that $xy$ means first apply $y$ and then apply $x$. This is left cancellative because the functions are one-to-one. To prove the existence of left common multiples, I'll prove a little more, namely that, for any $z$, there exists $x$ such that $xz$ is the function $n\mapsto2n$. Given $z$, it's easy to define such an $x$: On the range of $z$, it's defined (as it must be) by $x(z(n))=2n$; off the range of $z$, it maps everything in a one-to-one way into the set of odd numbers. Applying this construction to $z$ and also to a given $y$, we get the $x$ and $w$ needed for the left common multiples property. But right cancellation fails, because our maps need not be onto $\mathbb N$. Given any non-surjective $z$ in our monoid, we can construct $x$ as above and then, as the complement of the range of $z$ isn't empty, construct a different $x'$ that differs from $x$ at a point not in the range of $z$ but has $x'z=xz$.
For a countable example, just cut down to the set of arithmetically definable elements of this monoid. (By "arithmetically definable", I mean definable in first-order logic with symbols for addition and multiplication and with variables ranging over $\mathbb N$. The point is that all the constructions used above can easily be done definably.)