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)