Algorithm/function that returns random number in array in O(1) and creates single permutation

Intro: This is an interview question I had which I couldn't solve. A code solution will be good (in any language), but an algorithm/pseudocode is also great.

---

The problem: This problem is about designing an algorithm that solves the following problem:
You are given a function int getRand(int x) that gets an int x and returns an int in the range from 0 to x randomly (exclusively -> [0, k) ). Each call to getRand() is performed in O(1) time. You are also given an array int[] arr of size k containing integers.

Write a function getRandUnique() that when called will return a random member from arr such that after k requests exactly you will have a full permutation of the members of arr (this actually means that getRandUnique() will return a different member of arr for each call). Each call to getRandUnique() has to be performed in O(1) time.
You are allowed to use/store global variables etc...

E.g.: Assume arr = [2, 3, 5 , 1]. A call to getRandUnique() will return either 2, 3, 5, 1 in 1/4 probability. A consequent call to getRandUnique() will return on of the remaining 3 members in 1/3 probability and so on...

---

Attempt: I ended up managing to solve this myself (after much trial and error). I am posting the solution as well, but would love to get some other ideas/solutions. I will accept as the correct answer any solution that works (I don't want to accept my own)!

---

Question: How can this be achieved with all the above restrictions?