One possible solution could be to candy the herbs (though it’s a lot of work) or to soften the toffee by turning it into a kind of cream, freezing it separately, and then folding it into the ice cream at the last moment. This challenge is addressed in the article,
>We need to add sugar to the fruit to make sure it is softer than the ice cream itself – you don’t want to bite into ice cream and find a hard, frozen berry.
and considering you almost never see artisanal ice creams with chunks (unlike industrial ones like Ben & Jerry’s, for example), this is where culinary engineering becomes essential I guess.