but then I suffer from a "we dont trust you" penalty from all other races.
Breaking a peace treaty will only make the race you had it with no longer trust you. Only breaking the economic and research treaty will stop everybody from trusting you.
Is there a way to avoid this penalty? Is there a minimum number of turns to wait?
If you wait a year or so, it might be enough for them to not consider this a break of the treaty, but I'm not entirely sure. Usually, when I declare war it's permanent (until one side is gone), so there is no chance for a peace treaty (no matter how much they beg for it).
However, if you goad them into declaring war on you, you can avoid all of this. Just park some of your ships (especially troop transports) close to their planets, and they will declare war soon enough.
Is the penalty permanent or do races eventually trust you again?
It's permanent.