If you want a stateless way to shuffle, sorry, but that's impossible. A shuffle needs state. If you're content with random pairings that are independent of previous pairings then that can be stateless but it's not a shuffle. In that case your function is just an evenly distributed random number from 0 to length-1.
If you must have a shuffle, are willing to keep some state, but can't be moving users around in their array I have a solution.
Use indirection. You have arrays of users that you don't want to touch. Fine but they're arrays, so you have random access to them. You don't have to move the users. You just have to shuffle an array of indexes into one of them.
Say you have two arrays of 10 girls and 10 boys. Just add an array of 10 ints. Lets call it partner.
let partner = [0,1,2,3,4,5,6,7,8,9]
partner.shuffle()
Your 'function' is now partner[index]. You could use it like this:
dance(girls[index], boys[partner[index]])
Also, understand that in many languages if you shuffle your array of users you aren't actually moving around the user data. You're moving around a small little reference that points to the user data. That reference is usually no bigger than an int.
If you're in that situation then the indirection provided by partner is pointless. Just shuffle your array directly. If you can't because you have to preserve the original order you can simply make a copy of the references and shuffle the copy.
So be sure you can't directly sort your array before you add a level of indirection you might not need.
As for the issue of large, if you're up against more data then will fit in memory you might want to not assume you have full random access to the array. IO is slow and works better on large chunks.
A two pass shuffle can work on a chunk small enough to fit in memory. Populate the chunk randomly from the whole array, shuffle it, store it, move on to the next one. Here's a paper on it that comes with a rather nice visualization:
