You can use the Soft Body Goal in conjunction with a Vertex Group to 'pin' one or more vertex to the 'body' of the character - either directly (using Hook to Selected) or via an Empty.
Start by creating your character's body - in my case I'll stick with the default cube.
Create a leg as a string of vertices. The simplest way of achieving this is to add a Curve/Path and convert it to a mesh (select it and go to Object/Convert To/Mesh. Position it and scale it so that it is roughly in place. Add a plane for the floor, make it a Passive Rigid Body, and add Collision in the physics panel.
Select the 'leg' and subdivide it so it's got sufficient vertices to bend realistically but don't subdivide too much - the distance between vertices should ideally be comparable to the eventual 'thickness' of the 'legs'.
Next, in Edit mode (Tab), select the vertex at the top of the leg, press Control+H, for the Hook menu, and select Hook to New Object. This will create an Empty and hook the selected vertex to it.
While that single vertex is still selected go to the Mesh properties panel, add a new Vertex Group (click the '+') and Assign that vertex to the group. You can rename the Vertex Group to something appropriate by double clicking it and typing the new name (eg, 'Pin').
Swap back to Object mode (Tab), select the Empty, hold down Shift and select the 'body' - so that both are selected, and Control+P and Set Parent to Object to parent the empty to the 'body'. Moving the 'body' should now drag the vertex along with it. Move the 'leg' in position so it starts the simulation in the correct place.
Select the 'leg' and add Soft Body in the Physics panel. In the Soft Body Goal, set the Vertex Group to the 'pin' vertex group you created earlier. Set Soft Body Goal Strength and Goal Stiffness to their maximum values to bind the vertex strongly to the parent - the other vertices will be affected only by the Soft Body simulation.
Add Active Rigid Body physics to the 'body' or animate it with keyframes. The soft body leg will follow the motion of the 'body', pinned by the single vertex. You can add some variation to the leg (which assists with it 'folding' rather than getting stuck in a vertical line of perfectly aligned vertices) by selecting all vertices in Edit mode and selecting 'Randomize' in the Tool panel and setting a suitably small Amount of random variation.
Adjust the Soft Body Edges properties to tune the begaviour and stretchiness of the soft body. For example, increase the Pull spring strength to 0.9999 and maybe increase Bending Spring to, say, 0.5 to give the leg some resistance to bending. Also consider enabling Edge collision so edges don't pass through sharp edges of rigid bodies.
To give the leg some thickness, enable Soft Body Self Collision. The self-collision is based around a series of spheres around each vertex that repel other vertices. The size of the 'collision ball' around each vertex is usually based on the length of the edges connected - setting the Calculation to 'Average' will use the average spring length for the radius of the collision sphere and this is further adjusted by the Ball Size setting. Setting this to 0.45 (the default) and Average (the default) results effectively in spheres along the length of the soft body leg that almost touch when the leg is straight. This should give reasonable results providing the distance between the vertices are of a similar length to the intended thickness of the leg - otherwise adjust the Ball Size until you get the desired effect. Note, however, that ball sizes > 1.0 can produce strange effects since the ball will be larger than the neighbouring edge and will push away the adjacent vertices. If this occurs, reduce the number of vertices (so the spacing is close to the desired thickness of the soft body) and try again.
To generate a mesh around the 'leg' add a Skin modifier followed by a Subdivision Surface modifiers. To adjust the thickness of the 'skin', go into Edit mode, select all vertices (A) and press Ctrl+A or manually adjust the Mean Radius X/Y properties in the Properties panel (N). You can also add an additional Subdivision Surface modifier before the Skin to add additional smoothness to the coils (otherwise it can appear a bit angular).
Duplicate the same for the other 'leg'. Add Collision to the 'body' and adjust the collision on the 'body' and the 'floor' to set the 'Outer' Soft Body margin to match the thickness radius of the 'leg' - this will result in the appearance that the outer surface of the 'leg' collides with the surface (since it's actually the vertex that performs the collision, setting the 'Outer' to the radius of the soft body gives the surface a collision distance that matches what would occur if it were the outer edge of the soft body that was colliding).
Note : If you get strange behaviour with the soft body after changing the 'Hook' or the Soft Body settings, c heck the sequence of your modifiers since the order is very important. You should always have the Hook first, followed by the Soft Body, followed by the geometry modifiers (ie, Subsurface, Skin, etc.). In my case I used Hook, Soft Body, Subsurface (set to level '1' to smooth out the bends in the leg), Skin, Subsurface (set to level '2' to smooth out the Skin). It can also help to adjust the Soft Body Solver settings - decrease Error Limit (eg, from 0.1 to 0.01) and try increasing the Min Step (eg, 10 to 40) - vary one setting at a time and re-run the simulation to evaluate how this affects the simulation.
Blend file (free all bakes and re-run the animation to rebuild the Soft Body Cache) : 
