Obviously a wellorder cannot contain a copy of $\omega^*$ (the dual order of $\omega$), and this can be proven in ZF. In ZFC, it is easy to prove any linear order which is not a wellorder does contain a copy of $\omega^*$ (take a set with no minimum and keep picking smaller and smaller elements), but this proof depends quite essentially on choice. There doesn't seem to be any way of proving it without choice, so it seems quite likely that this is not provable in ZF.
If it is unprovable in ZF, that would imply there is a model of ZF with a linear order not containing $\omega^*$ which is nonetheless not wellordered. So I would like to know that this is indeed unprovable in ZF, and what such a linear order might look like.
This question seems rather beyond my own mathematical abilities, but I am very curious. I have tried to prove independence of ZF by seeing if I can prove something choicy using the statement that any linear order not containing $\omega^*$ is wellordered, but that approach doesn't seem helpful as I can't construct a linear order on any set not containing $\omega^*$ without choice.
In Cohen's first model there is an infinite Dedekind finite set of reals. Being Dedekind finite means that it has no countable subset, increasing or decreasing.
But on the other hand, any infinite well order has a copy of $\omega$. So as a linear order, inherited from the reals, it satisfies your requirements.