METAL GEAR SOLID 3: Snake Eater - Master Collection Version

Here is the list of every face paint in the game. First and foremost, when selecting a new game, make sure to pick "I like MGS3!" as this will give you an additional batch of masks to start with.

Zombie
Location: Rassvet
During Operation: Snake Eater, go to the top of the map behind the burnt out building. It's behind the movable flammable barrel.

Snow
Location: Bolshaya Past Base
This is the base with a helipad and a parked Hind. Follow the ditch the encircles the base and you will find it beneath a small footbridge.

Desert
Location: Ponizovje Warehouse
Lowest floor of the warehouse.

Oyama
Location: Graniny Gorki 1F.
From the small courtyard inside the building, inside the vent that connects it to the outer area of the base.

Water
Location: Ponizovje South.
In the mangrove swamp (the channel where the water is waist-high with trees, not cliffs, on either side). You need to backtrack all the way back there after defeating The Fear.

Kabuki
Location: Tikhogornyj
After losing your gear and meeting EVA, backtrack behind the little waterfall and dive into the pool beneath it. It's at the bottom of the pool.

Infinity
Location: New Game+
No, seriously. You need to capture a live Tsuchinoko and hold on to it until the end of the game. There are a couple of places to find it, but the one that I had the best luck was in the area where you fight The Fear. When you first come through at night, place as many animal traps as you have. Leave and then return. It is random if you catch the critter or not. Just keep emptying the traps and resetting them until you grab it.

Here's a video showing how to capture it: Video credit goes completely to AceMGO.

Then, once meeting EVA behind the waterfall (see Kabuki face paint) go back outside and on the moss near the waterfall you should see the Tsuchinoko slithering around on the ground. Tranq. it and capture it. DON'T EAT IT! Just keep it in your inventory until the end of the game.

If anyone is really curious about the Tsuchinoko's origins (as I was) here's a brief description of it: https://en.wikipedia.org/wiki/Tsuchinoko