CJam (6 * 240 = 1440)
5e!72>
Online demo, validation (outputs the index at which each permutation of 0..4 can be found; it needs to flatten the output because the original program gives suitable output to stdout but what it places on the stack is not directly usable).
Approach stolen from Sanchises, although the permutation order of CJam is different, giving a different substring.
CJam (22 * 207 = 4554)
0a4{)W@+W+1$)ew\a*W-}/
Dissection
This uses a simple recursive construction.
0a e# Start with a superpermutation of one element, [0]
4{ e# for x = 0 to 3:
) e# increment it: n = x+1
W@+W+ e# wrap the smaller superpermutation in [-1 ... -1]
1$)ew e# split into chunks of length n+1
\a* e# insert an n between each chunk
W- e# remove the -1s from the ends
}/