The question can be interpreted in a few different ways: both what you mean by having the $xy$ slices of the 3-space Euclidean, and what you mean by it being non-Euclidean in the $z$ direction.
The suggestion of taking a Euclidean plan and cross it with a non-Euclidean curve only works if you look at the global structure. Any (smooth) curve is locally Euclidean, i.e. you can straigten it out, so locally the 3-space will be Euclidean. However, if you take $\mathbb{R}^2\times S_1$, i.e. Euclidean plane times a circle, it will not be the same as Euclidean $\mathbb{R}^3$.
However, I suppose what you had in mind was local geometry, not global geometry. Normally, by saying locally Euclidean, we just mean that in an infinitessimal neighbourhood of any point, the space is Euclidean. I'm not completely sure if this necessarily will always allow you extend this to a bigger region (of positive size, although perhaps small).
Another question is if the $xy$ slice itself is Euclidean, i.e. has an Euclidean metric, or if the embedding into the 3-space should also be non-curved.
Let me give you a few examples and discuss them. The way I describe the metric, i.e. distance function, on 3-space parametrised by $(x,y,z)$ is on the form $$ds^2=dx^2+dy^2+dz^2 \iff s'=\sqrt{(x')^2+(y')^2+(z')^2}$$ where $ds$ is the infinitesimal distance between $(x,y,z)$ and $(x+dx,y+dy,z+dz)$, and the length of a path $(x(t),y(t),z(t))$ is computed by integrating $s'$. 586
This is the Euclidean metric on 3-space.
An alternative metric I can make is $$ds^2=f(z)^2\cdot(dx^2+dy^2)+dz^2$$ which means the $xy$ plane is scaled by a factor $f(z)$. Note that if we enter new coordinates $u=f(z)\cdot x$, $v=f(z)\cdot y$ and restrict attention to the surface with constant $z$ (i.e. all $dz$ terms disappear), we find the metric on the surface $S_z$ to be $ds^2=f(z)^2\cdot(dx^2+dy^2)=du^2+dv^2$, so this is still a Euclidean plane. However, in the function $f(z)$ is non-constant, the 3-space is curved. What's more (and perhaps less intuitive) is that the $S_z$ planes lie curved inside the 3-space. One way to see this is that the shortest path between two points in $S_z$ will tend to leave $S_z$ and take a short-cut through the side of $S_z$ in 3-space for which $f(z)$ is lower: on this side, distances are shorter, just as the shortest path between to points on a circle in the plane will pass through the interior of the circle rather move along the circle.
Another metric we can make is $$ds^2=dx^2+dy^2+h(x,y,z)^2\cdot dz^2$$ for some arbitrary positive function $h(x,y,z)$. Again the constant $z$ slices, $S_z$, are Euclidean planes: this time with no scaling involved. Instead, distances along the $z$ direction are scaled. This time, the embedding of the $S_z$ planes itself is non-curved: not only is the metric on $S_z$ equal to $ds^2=dx^2+dy^2$, but there are no short-cuts by passing out of $S_z$.
Mathematically, the curvature is described locally by the Riemann curvature tensor. This is based on the idea of parallell transportation of vectors: i.e. if I start at a point $P$, pick a direction $u$ (described by a tangent vector) and another vector $w$, I can parallell transport $w$ in the $u$ direction: say to a point $P+\epsilon u$. 586