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.
An interpolation by cubic splines has enough degrees of freedom to do what you need. You decompose your domain $[0, 1]$ into intervals $[x_i, x_{i+1}]$, corresponding to your control points. Now, on each interval you define a cubic function
$$s_i(x) = a_i x^3+b_i x^2+c_i x+d_i.$$
To compute the coefficients, you have to apply your constraints:
$$\begin{align} s_i(x_i) &= y_i \\
s_i(x_{i+1}) &= y_{i+1}\\
s_i'(x_{i+1}) &= s_{i+1}'(x_{i+1})\end{align}$$
This gives you two conditions per cubic for the position and one for the tangent continuity, except for the first and last, where there's no tangent continuity condition.
These aren't enough conditions yet to give a unique solution, as you need 4 conditions for each cubic to determine the 4 coefficients. Ignoring your requirement to stay inside [0, 255] for a second, a common way to interpolate is the "natural" cubic spline, which additionally requires continuity of the second derivative and sets the second derivative to zero at the end-points to give a complete equation system. You would then have to solve that linear system of equations. An alternative are Catmull-Rom splines, which are local and thus don't require solving a linear system.
This does not address your "no overshooting" requirement. You can ignore the second derivatives from the cubic spline and try to work this requirement into the system instead. However, this does not uniquely define your function. One solution to fulfill your requirements is to set the tangents to zero at each control point:
$$\begin{align} s_i(x_i) &= y_i \\
s_i(x_{i+1}) &= y_{i+1}\\
s_i'(x_{i}) &= 0\\
s_i'(x_{i+1}) &= 0\end{align}$$
This will give you sigmoidal shapes for each interval and prevent overshooting. However, it will not look very pretty, it has way too much tension (The natural spline will have minimal tension).
A better solution might be to start with a "good" interpolant like the Catmull-Rom spline and then compute its representation in B-Spline form. B-Splines (like Bezier curves) have the convex hull property. This means, the curve will never be outside of the convex hull of the control points. You can use this to prevent over-shooting. Just ensure that the y-coordinate of your B-Spline control points are in [0, 255]. If the control points you got from computing the spline are outside this range, just set them to 0 or 255 accordingly.
In many vector graphic tools like Inkscape you can draw cubic splines and manipulate the corresponding control points, so you can toy with it there to get a feeling what you need.
Best Answer
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.