If losing electrons means getting oxidized, then does it mean that ALL metals are reducing agents, since they themselves get oxidized? I was just going through my last year's school textbooks and while I was reading this chapter on Redox, this above question crossed my mind.
Shouldn't it be true that since ALL metals lose electrons to get stable, they should also get oxidized. And since they getting oxidized themselves, they should act as reducing agents... Always?
If the answer is no, please provide an example of the exception.
Your reasoning is sound. All (pure) metals can act as reducing agents, but they do not have to all the time. There are a few examples of metals in negative oxidation states, where they would act as oxidising agent.

Probably the most prominent examples are Zintl phases, where alkaline or earth alkaline metals reduce post transition metals (or metalloids like antimony). One of the first reactions observed was the sodium lead reactions in liquid ammonia in 1907. Back in the day they proposed the following reaction equation:
$$\ce{Na + excess~Pb ~-&gt;[\ce{NH3}][\mathrm{-50^\circ C}]~ Na+ + $“$~Pb2^{-}~$”$}$$
It was later found that the actual composition is $\ce{Na4Pb9}$. With crown ethers and/or cryptants it is possible to isolate discrete anions, too.

There are more examples like this, and a nice overview is given in John E. Ellis, Inorg. Chem., 2006, 45 (8), 3167–3186.