MYSQL 5.7 Partition a table based on partition key of another related table
NOTE:  FOREIGN KEYS are not allowed in partitioned tables.  Simply drop the FKs but keep the indexes that they generated.  Presumably, the FK checks are redundant now that you have debugged your app.

adding an additional column t_execute_on_date is just not possible.

See pt-online-schema-change or gh-ost.
Using PARTITIONs is the optimal way to delete &quot;old&quot; data from the history table, but there are other approaches:  http://mysql.rjweb.org/doc.php/deletebig
The one that comes to mind is to have a continually-running job that keeps looking at the &quot;next 1000&quot; rows to see if any of them should be deleted.  (It must walk through the table using the PRIMARY KEY.)  It might do a LEFT JOIN to see which ones are gone, as hinted at in this pseudo-code:
$a = 0;
Loop...
    $z = SELECT th_id FROM transaction_history order by th_id LIMIT 1000,1;
    exit loop if $z IS NULL
    SELECT th_id
        FROM      transaction_history AS the
        LEFT JOIN transaction AS t  ON th.t_id = t.t_id
        WHERE t.t_id IS NULL
          AND th.th_id &gt;= $a
          AND th.t_id   &lt; $z
    DELETE those rows -- probably better to do this as a single query
$a = $z;

When you exit the Loop, simply start over.
The hope is that this approach to deleting &quot;old stuff&quot; will be fast enough to keep up, though there will be some lag.
Still, I would hope that pt-online-schema-change or gh-ost can turn a non-partitioned table into a partitioned table with minimal downtime, regardless of table size.  (No FKs.)
Caution:  The optimal indexes for a partitioned table are usually different than the equivalent non-partitioned table.  Toss any unused tables when adding partitioning; there is some overhead when building a table with the secondary indexes already in place.