Here's a completely different and non-bruteforcing approach, so I'm adding it as a separate answer.
Helper function:
help[list_] := Join[{First@list}, #] & /@ Rest@list
Main function:
iterate[list_List /; Length@list < 3] := {{list}}
iterate[list_List /; Length@list > 3] := Module[
{sublists =
iterate /@ (Delete[list, {{1}, {#}}] & /@
Range[2, Length[list]]), inter},
inter =
MapThread[
Prepend, {sublists, ({First@list, list[[#]]} & /@
Range[2, Length[list]])}];
Flatten[help /@ inter, 1]
];
Timing:
iterate[Range[14]] // AbsoluteTiming // First
6.89226
As compared to belisarius' approach, where a list of 12 elements takes about 38 seconds on my machine.
The algorithm is quite simple. Take the first element and pair it with the second, find all partitions of the remaining elements (3 to n). Append the 1st and 2nd element to these partitions. Then add to that the result of doing the same with the 1st and 3rd, 1st and 4th... 1st and nth.