My ISP uses a software that replaces site certificates with it own certificate so secure pages are always untrusted. Is there any solution for this? Is it safe to proceed with the resulting sites (including gmail)?
No, proceeding is not safe; your ISP is performing a man-in-the-middle attack on your encrypted traffic, and can therefore read all traffic if they choose so.
Yes: Get a new ISP.
As a side note:
I am very surprised; I have never heard of an ISP doing this, and I would not even consider such a company a proper ISP (since they don't provide the service of an ISP, which is sending and receiving the data that you send or want to receive).
What ISP is this? I can't imagine any regular ISP doing this.