Your second calculation is wrong. Basically because you have to be a little bit more careful what you are taking the trace of! You use the anti-commutation relations for the Dirac matrices, which is commonly written down like $$ \{\gamma^\mu, \gamma^\nu\} = 2 g^{\mu\nu}, $$ which is actually a bit sloppy. There is a $\mathbb I$ missing. You can easily see this observing that on the left there are matrices (which are entries of a 4-vector) and on the right there is only an entry of a tensor so there must be the identity. Hence you end up with $$ \text{tr}(\gamma^\mu \gamma^\nu) = \text{tr}(\{\gamma^\mu, \gamma^\nu\} - \gamma^\mu \gamma^\nu) = \text{tr}(2g^{\mu\nu}\mathbb I) -\text{tr}(\gamma^\mu\gamma^\nu) $$ $$ \implies\text{tr}(\gamma^\mu\gamma^\nu) = \frac{2}{2} \text{tr}(g^{\mu\nu} \mathbb I)=4g^{\mu\nu} $$

Your second calculation is wrong. Basically because you have to be a little bit more careful what you are taking the trace of! You use the anti-commutation relations for the Dirac matrices, which is commonly written down like $$ \{\gamma^\mu, \gamma^\nu\} = 2 g^{\mu\nu}, $$ which is actually a bit sloppy. There is a $\mathbb I$ missing. You can easily see this observing that on the left there are matrices (which are entries of a 4-vector) and on the right there is only an entry of a tensor so there must be the identity. Hence you end up with $$ \text{tr}(\gamma^\mu \gamma^\nu) = \text{tr}(\{\gamma^\mu, \gamma^\nu\} - \gamma^\mu \gamma^\nu) = \text{tr}(2g^{\mu\nu}\mathbb I) -\text{tr}(\gamma^\mu\gamma^\nu) $$ $$ \implies\text{tr}(\gamma^\mu\gamma^\nu) = \frac{2}{2} \text{tr}(g^{\mu\nu} \mathbb I)=4g^{\mu\nu} $$ See also chapter 3.2 in "An Introduction to Quantum Field Theory" by M. Peskin and D.Schröder. (In my edition it is page 40)