Generating versions of an array with elements changed in ruby
Ruby, 102 99 98 95 bytes

(k=input.map &amp;:dup)[$.-=1][0]=%i[nop jmp acc][k[$.][0]&lt;=&gt;:jmp]until(r=try_with k||$:)[1]&gt;:t;p r

Try it online!
I assume that input and try_with are mandatory names for the Advent of Code challenge. If not, the code can obviously be even shorter. Here, I also assume that the try_with method will accept invalid input, that is, an array whose elements are not of the form [:instruction, integer]. See below for a slightly longer version in case try_with strictly requires valid input.
See commented code below for a complete list of ideas used. Apart from generic code-golf tips such as 'use short variable names', or common Ruby tips such as 'omit parentheses in method calls', here are some specific tips for the problem posed:

Instead of each_with_index, use a counter variable together with an anonymous lambda and redo together with until (or while) in modifier form. For the counter, a good choice in this case is the predefined global variable $., which is initialised to 0. Processing the input array in reverse (by decrementing $. in place) is the best approach. Incrementing $. in place doesn't work (because input[0] would be skipped); incrementing $. at the end of the loop would cost bytes.
Only call dup at the lowest level, that is, on the elements of input, not on input itself.
Lexicographical comparisons work with symbols, so &gt;:t is better than == :terminate, for example.
It turns out to be slightly shorter to use the spaceship operator &lt;=&gt; instead of a ternary conditional to choose between instructions. In the code, k[$.][0]&lt;=&gt;:jmp returns -1 if the current instruction is :acc, 0 if it is :jmp, and 1 if it is :nop. Use these values to index into an array of the three symbols, ordered such that the correct replacement is chosen.

(k=                # use parentheses to define variables inline
   input.map &amp;:dup # only duplicate the lowest-level arrays, and do all at once
)[$.-=1][0]        # use $. as a counter and decrement in place                       
=%i[nop jmp acc][k[$.][0]&lt;=&gt;:jmp] # use the spaceship operator to choose between instructions            
until              # loop with until
(r=try_with k      # omit parentheses in the call to try_with
||$:)[1]           # on the first iteration (only), k is nil so pass the predefined array $: to try_with as dummy input
&gt;:t;               # test for &gt;:t instead of ==:terminate
p r                # print the result


Ruby, 98 bytes

p-&gt;{(k=input.map &amp;:dup)[$.-=1][0]=%i[nop jmp acc][k[$.][0]&lt;=&gt;:jmp];(r=try_with k)[1]&gt;:t||redo;r}[]

Try it online!
Use this version if try_with rejects $: as valid input. Here, we iterate using an anonymous lambda and redo.