The fundamental object that underlies all of this is the metric on your space. Basically, it tells you the infinitesimal separation between two points with infinitesimal coordinate separations $dy_1$, $dy_2$, and $dy_3$. For example, in Cartesian coordinates, you have the familiar metric
$$
ds^2 = dx^2 + dy^2 + dz^2,
$$
while in spherical polar coordinates you have
$$
ds^2 = dr^2 + r^2 \, d\theta^2 + r^2 \sin^2 \theta \,d \phi^2.
$$
Notice that for spherical polar coordinates, you have functions of the coordinates in front of the $d\theta^2$ and $d\phi^2$ terms. This suggests that the most general possible thing you can do* is to write down a metric of the form
$$
ds^2 = h_1^2(y_i) \, dy_1^2 + h_2^2(y_i) \, dy_2^2 + h_3^2(y_i) \, dy_3^2
$$
where the $h_i$ functions are functions of the coordinates themselves.
Importantly, it's possible to write down metrics which correspond to displacements on spaces without a set of Cartesian coordinates. For example, if I want to look at displacements on the surface of a sphere of radius $R$, I can just set $r = R$ and $dr = 0$ in the above metric for spherical polar coordinates:
$$
ds^2 = R^2 \, d \theta^2 + R^2 \sin^2 \theta \, d \phi^2.
$$
It's impossible to define a pair of (two) Cartesian coordinates on the (two-dimensional) surface of a sphere, because the sphere has curvature in a mathematical sense. But this metric is still a valid metric for the surface of a sphere.
Despite this lack of underlying Cartesian coordinates, it's still possible to then write out equations for gradients, curls, Laplacians, etc. on a curved manifold without any reference to any underlying Cartesian coordinates. For example, the Laplacian of a scalar field on an arbitrary curved manifold is
$$
\nabla^2 \phi = \frac{1}{h_1 h_2 h_3} \left[ \frac{\partial}{\partial y_1} \left( \frac{h_2 h_3}{h_1} \frac{\partial \phi}{\partial y_1} \right) + \frac{\partial}{\partial y_2} \left( \frac{h_3 h_1}{h_2} \frac{\partial \phi}{\partial y_2} \right) + \frac{\partial}{\partial y_3} \left( \frac{h_1 h_2}{h_3} \frac{\partial \phi}{\partial y_3} \right) \right]
$$
Deriving this result without referring to a set of underlying coordinates requires a fair amount of mathematical machinery that is a little hard to wrap your head around; but it's necessary if you're dealing with spaces with curvature.
In particular, this machinery is essential in general relativity, where spacetime is curved in this mathematical sense. An introductory GR textbook such as those by Schutz, Wald, or Carroll can tell you all about these techniques if you're interested; but be aware that it's pretty dense.
*This isn't actually the most general thing you can do---I've restricted to what are called orthogonal coordinates here---but it's close enough for the purposes of this answer.
