One may always choose any coordinates on a spacetime manifold or any other manifold, for that matter. That's not only a simple mathematical insight but also a cornerstone of the general theory of relativity. In fact, GR starts with the postulate that all (non-singular etc.) coordinate systems are as good as any other coordinate systems and the basic laws of physics should have the same (and equally simple) form in all of them. This democracy is known as the "general covariance" and the fact that GR respects this principle is why it's called the general theory of relativity.
In cosmology, we may want one of the coordinates to be a cosmic time $t$ whose constant value may specify the same moment in the whole Universe – the same time since the Big Bang, as reflected e.g. in the local temperature which is a function of $t$. When we add the assumption that $t$, one of the coordinates is a cosmic time, we're adding some extra information about the space. Anti de Sitter space or de Sitter space or other spacetimes may admit various slicings to "cosmic time", even with different signs of the spatial curvature of the slices.
What allows us to create an embedding and invoke arbitrary coordinates on it within it's 'larger' Minkowski space?
This question seems to implicitly assume that the larger Minkowski space into which you embedded the anti de Sitter space plays a physical role. But it doesn't play any role. It's nothing more than one of the many ways to visualize the anti de Sitter space and its shape (although arguably a particularly simple one). It is not a "real" space. The spacetime or the Universe is everything there is; so if the spacetime is an anti de Sitter space, it means that there is no "larger space outside it". And coordinate systems on anti de Sitter space are not "obliged" to resemble the coordinates $X_0,X_1,\dots$ on your larger Minkowski space. In fact, the physically natural and useful coordinate systems almost never do.