CJam (22 * 207 = 4554)
0a4{)W@+W+1$)ew\a*W-}/
Online demo, validation (outputs the index at which each permutation of 0..4 can be found).
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
}/