It looks like your set of endpoints and control points can be
any set of points in the plane.
This means that the $order$ of the points
is critical,
so that the generated curve goes through the points
in a specified order.
This is much different than the ordinary interpolation problem,
where the points
of the form $(x_i, y_i)$
are ordered so that
$x_i < x_{i+1}$.
As I read your desire,
if you gave a set of points on a circle
ordered by the angle of the line
from the center to each point,
you would want the result to be
a curve close to the circle.
There are a number of ways this could be done.
I will assume that
you have $n+1$ points
and your points are $(x_i, y_i)_{i=0}^n$.
The first way I would do this
is to separately parameterize the curve
by arc length,
with $d_i = \sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2}$
for $i=1$ to $n$,
so $d_i$ is the distance from
the $i-1$-th point to the
$i$-th point.
For a linear fit,
for each $i$ from $1$ to $n$,
let $t$ go from
$0$ to $d_i$
and construct separate curves
$X_i(t)$ and $Y_i(t)$
such that
$X_i(0) = x_{i-1}$,
$X_i(d_i) = x_i$,
and
$Y_i(0) = y_{i-1}$,
$Y_i(d_i) = y_i$.
Then piece these together.
For a smoother fit,
do a spline curve
through each of
$(T_i, x_i)$
and
$(T_i, y_i)$
for $i=0$ to $n$,
where
$T_0 = 0$
and
$T_i = T_{i-1}+d_i$.
To get a point for any $t$ from
$0$ to $T_n$,
find the $i$ such that
$T_{i-1} \le t \le T_i$
and then,
using the spline fits
for $x$ and $y$
(instead of the linear fit),
get the $x$ and $y$ values from their fits.
Note that
$T_i$ is the cumulative length
from $(x_0, y_0)$
to $(x_i, y_i)$,
and $T_n$ is the total length of the line segments
joining the consecutive points.
To keep the curves from
not getting too wild,
you might look up "splines under tension".
Until you get more precise,
this is as far as I can go.
Your requirements are somewhat conflicting. #1 and #2 would lead you to use some sort of arc-spline. This is a "spline" that's composed of a sequence of circular arcs joined end-to-end. See here or here or here for more info. It is common to use a "bi-arc" construction to build arc splines. An early paper on bi-arcs is this one. You can refer to it and later papers that cite it. Using circular arcs is the simplest way of getting easy arclength computations.
But arc splines will only be tangent continuous, at best; they will have discontinuities of curvature. So, they violate your condition #4. If you use a large number of circular arcs then these discontinuities will be small, so they may be tolerable for your application. Only you can decide. A word of warning: there is only a flimsy relationship between continuity of derivatives and visual/aesthetic smoothness. So, if visual smoothness is what you really want, it might be fine to give up on C2 continuity.
If you really need continuity of second derivatives (requirement #4), you are forced to use more complex curve segments to build the spline. The most common choice would be cubic segments (i.e. parametric cubic splines). These will give you C2 continuity, but calculating arclengths will require numerical methods. Cubic splines are somewhat easier to construct than arc splines, and lots of software is available to help.
If you're willing to do some work, you could try constructing so-called "Pythagorean Hodograph" curves. These are special polynomial splines whose arclength functions are polynomials. I guess they give you everything you want, but constructing them is fairly complicated. A good starting point is this book and other papers by Rida Farouki.
So, you can have easy construction, continuity of derivatives, speed of arclength calculations. Pick two.
Best Answer
Cubic Hermite curve seems to be right for the purpose. A cubic Hermite curve is defined by a series of points and first derivatives at these given points. A cubic Hermite curve is a piecewise continuous curve (in general only C1) and each segment (the portion between two successive points) is in fact a cubic polynomial. See this link for more details. It is easy to implement and the best thing is adding a new point will not affect the shape of the previous segments. If you do not know what first derivative value should be used for any point, you can use finite difference method to infer it.