How to put breakpoint at random instruction

I have to do this, repeatedly many times:

1. Start execution of program
2. Stop at random point during execution
3. Modify value in register
4. Continue execution

Until now, I've been using GDB extended with Python and the only struggle is to stop randomly during execution.

Already tried approaches:

• Retrieve binary file sections and pick random address among executable instructions. ----> Problem: too low probability of hitting set breakpoints, takes too long to obtain valuable results.
• Break at _start and do stepi {rand_num} to skip {rand_num} instructions, then alter register. ----> Problem: infeasible, programs under test contain too many instructions, too long test execution time.
• Send signal SIGINT to the inferior process, after waiting a random amount of time. ----> Problem: programs under test execute in less than 30ms, problems with temporization.

How would you do? Which tools would you use?

Thank you in advance! :)