  Kingman (1978)'s representation theorem states that any exchangeable
partition of $\mathbb{N}$ can be represented as a paintbox based on a random
mass-partition. Similarly, any exchangeable composition (i.e. ordered partition
of $\mathbb{N}$) can be represented as a paintbox based on an
interval-partition (Gnedin 1997). Our first main result is that any
exchangeable coalescent process (not necessarily Markovian) can be represented
as a paintbox based on a random non-decreasing process valued in
interval-partitions, called nested interval-partition, generalizing the notion
of comb metric space introduced by Lambert & Uribe Bravo (2017) to represent
compact ultrametric spaces. As a special case, we show that any
$\Lambda$-coalescent can be obtained from a paintbox based on a unique random
nested interval partition called $\Lambda$-comb, which is Markovian with
explicit transitions. This nested interval-partition directly relates to the
flow of bridges of Bertoin & Le Gall (2003). We also display a particularly
simple description of the so-called evolving coalescent (Pfaffelhuber &
Wakolbinger 2006) by a comb-valued Markov process. Next, we prove that any
measured ultrametric space $U$, under mild measure-theoretic assumptions on
$U$, is the leaf set of a tree composed of a separable subtree called the
backbone, on which are grafted additional subtrees, which act as star-trees
from the standpoint of sampling. Displaying this so-called weak isometry
requires us to extend the Gromov-weak topology of Greven et al (2006), that was
initially designed for separable metric spaces, to non-separable ultrametric
spaces. It allows us to show that for any such ultrametric space $U$, there is
a nested interval-partition which is 1) indistinguishable from $U$ in the
Gromov-weak topology; 2) weakly isometric to $U$ if $U$ has complete backbone;
3) isometric to $U$ if $U$ is complete and separable.
