Put the line in the code you nut and shake it all up
CJam, 120 valid permutations, 334 299 290 bytes
&quot;She put the lime in the coconut, she drank them both up&quot;N+
&quot;Brother bought a coconut, he bought it for a dime&quot;N+]$~
&quot;She put the lime in the coconut, she drank them both up&quot;N+
&quot;His sister had another one, she paid it for a lime&quot;N+]$~
&quot;She put the lime in the coconut, she drank them both up&quot;N+

Pretty simple logic:

Put each line of the song in each of the 5 programs
Wrap everything on stack in an array
Sort the array
Unwrap the array so that the next program can use the same logic
In each step, we have the partial lyrics in an array. Luckily, sorting the array gives the correct order of the lyrics.

UPDATE: Turns out that you don't need the wrap-sort-unwrap cycle after the 3 similar and appearing at the end lines of the song. I can explain why if its not that apparent :)