If you just want to insert an element at the beginning of the list you can use the original list as the tail of the new list. It's immutable, so it's not going to change under you.

If you want to insert stuff randomly, you wouldn't use lists to get the best results in a functional setting. You might use something like finger trees instead.