The right time/place to do this is in the qtype_..._queestion class, not the qtype_... class.
The start_attempt() and apply_attempt_state() methods exist for this purpose. https://github.com/moodle/moodle/blob/master/question/type/questionbase.php#L168
start_attempt gets called when a new attempt at the question is started. You can do any necessary updates to the question data for this specific attempt (e.g. this is where multichoice shuffles the choices). Any data you would need later to restore this state must be stored in the $step object using $step->set_qt_var(). Core qtype_calculated is an example: https://github.com/moodle/moodle/blob/master/question/type/calculated/question.php#L54 - the code that does the real work is https://github.com/moodle/moodle/blob/master/question/type/calculated/question.php#L145.
Then, to make things like processing submitted data and review work, you also need to implement the apply_attempt_state method. The should take the data out of where you stored it in the initial $step, and use it to update the question to match what it was after start_attempt.
If each question only has a few different random variants, then it would be best to let Moodle do the random selection for you. You need to implement the get_num_variants method, and then use the $variant argument passed in to start_attempt to say which random variant is used. The reason to do this is that it makes the quiz statistics report more useful.
Like most things in the question system, the best documentation for the details is in the PHPdoc comments on the methods in the base class (e.g. https://github.com/moodle/moodle/blob/master/question/type/questionbase.php#L168)