Please look if my following argument is correct, otherwise point to my mistakes!
I distinguish two cases:
We have nothing but logic, i.e. we have an empty set of premises. And here the answer seems clear: yes, we can always introduce tautologies like p v ~p. So in such a scenario we can "create" something out of nothing. So in such a scenario God could have created the world out of nothing, because the world can certainly be seen as a tautology of the form: things that are or things that are not.
We have nothing, not even logic. But then logical impossibility seems impossible itself because you need logic to be able to get contradictions. That means a creatio ex nihilo in that sense is not logically impossible, but only unlogically. So even here a theologian could point out that God doesn't act contradictory when he creates the world (which is important because by christian dogma God cannot do logically impossible things, but he wouldn't need to do as we have just seen).
So overall a creatio ex nihilo seems not logically impossible which means that its opposite 'nihil ex nihilo' (nothing comes from nothing) is NOT a tautological truth.