To the best of my knowledge there is no universally agreed upon precise definition of the word "fractal", so it's not clear to me exactly what would or would not constitute an example of a fractal that is not embedded in Euclidean space.  

However, the various quantities referred to as "fractal dimension" -- Hausdorff dimension, box dimension, etc. -- do not actually require an ambient Euclidean space for their definition.  All you need is a metric on the set X under consideration -- this is enough to define "balls of radius r", and once you can do that the definition of Hausdorff dimension, box dimension, etc. goes through exactly as in the Euclidean case.

In fact, there's a very general framework for all these dimensional quantities (for me the standard reference is "Dimension Theory in Dynamical Systems" by Yakov Pesin), which can be formulated in a setting completely independent of Euclidean space.

As a possible example of a "non-Euclidean fractal", I would consider the symbolic space $\Sigma_2^+ = \{0,1\}^\mathbb{N}$ with a metric such as $d(x,y) = 2^{-t(x,y)}$, where $t(x,y)$ is the first coordinate in which x and y differ.  This is homeomorphic to the Cantor set but not embedded in Euclidean space.