How to make / generate the trailing effect?
I can't fully get you reference to your freestyle setup, but a simple way could be using a mesh deformed by and also following the curve, using a blend texture influencing the mesh alpha.
This is a single color example, but it should be possible use a rainbow style texture...

you could combine such a trail with the freestyle based animation, perhaps... maybe using different render layers.
edit: since you asked here is a possible similar setup with cycles (renders a bit slower)

edit: since you asked, here is the .blend related to the last example (cycles)

Note: the animation is not done with follow path here, but animating the Y location after setting a curve deform modifier... the effect is similar, though.