While there are some good answers here I wanted to add my experience into the mix.
What is metagaming?
(I feel really strongly about this). The community have over the years co-opted what the term Metagame means. Inherently Metagaming (per its definition) is what game designers use to ensure the rules of the game are balanced and fair. Meta gaming deals with advance strategy and, most importantly for the playing group, metagaming forms part of the inherent social contract between players and GM: that the game is a shared, noncompetitive experience. The players work together.
The GM presents obstacles but isn’t actively invested in the players’ failure. And so on. The interactions at the table and the social rules that govern them? Those are part of the metagame.
Answering using 'Metagame' as implied by the question
Now for the answer: I will use the phrase Metagame in the context that the community has decided to use it for: an idea that a player's decisions for their character are made with some outside non-game knowledge and therefore spoil the game.
Your question makes an assumption that the situations you describe are either a problem, or reflect a behaviour the players need to change. I would challenge that by saying that each of the issues you describe either isn't an issue at all (in anyone's other then a DM's head) or is a situation that is brought about because of the DM.
As a trivial random encounter is winding down, a player thinks "That
was too easy... The GM wouldn't give us an encounter that doesn't give
XP," and starts searching for hidden bad guys or other clues.
Investigating an area after a combat is not metagaming. The whole idea of an adventurer, early on, is that they survive off the land, by finding anything they can make use of. Corpses are looted, rooms searched, etc. Expecting your players not to search after an encounter because in your head it is random makes little sense in that context. Do you have to provide something if there is nothing? No.
I have had players roll a 20 for investigate after killing an enemy, they find no more then they would have if they rolled the DC of 8 I had set in my head, sometimes all that is ther is a few pinecones and a half-eaten deer. If players are constantly looking around, hunting for something, that suggests to me as a DM that either my encounters are not actually delivering anything of any value to the characters, they are not learning anything here, or the players themselves are getting bored. Any of that suggests that as a DM I need to change my behaviour mix things up a bit, or just stop rolling the random encounters table.
There are four statues in a room, and you use miniatures to represent
them. The players think to themselves "Well if the GM used miniatures,
these things are definitely coming to life," and get ready to fight.
Again is this metagaming? Adventurers live their lives on the edge of combat, expecting danger around every corner. They live with a knowledge that at anytime anything could be waiting to kill them. It is why we allow them to spend their entire life stealthing everywhere, checking for traps every two minutes. As a DM I don't accuse my players of metagaming when they tell me I stealth down this cavern, or I stealth through this wood. I accept that as part of the Darwinism that is being a successful adventurer - the characters "in-universe" would be very cautious.
Your players enter a room with 4 statues. You make a point of describing them in detail which means that the characters have really taken in statues as being of interest which would instantly make the adventurers feel concerned. These are different, unusual; it is perfectly believable that, by being so special, they warrant the players taking a close interest. The characters would be wary, they know magic happens, they search for traps constantly, so these statues might be a trap. Expecting players to behave differently means for them to play their characters as suddenly ignoring their environment.
But as A DM I want to provide a shocking surprising moment, I want this to be unexpected.
There are plenty of ways you can do this. The first way is to put statues everywhere and put them on the map, describe the first, normal stone ones in detail as part of your description of the background. The characters will just see everything as just another statue. They may still approach every statue with caution but this is what adventurers do if they intend to survive; it isn't necessarily the player acting against what there character would do. Using that
kind of description will also train your players that things put on the battle map are not always more then "just a statue."
The other way: don't put the statues on the map until they come to life, describe them when they enter the room but, if you don't usually place statues on the board don't do it now. By putting them on the board you make into items them of interest to the characters. Why? It is a part of the environment that stands out. You are telling your players, as part of the story, that these things here are important. Expecting characters to wander around aimlessly and ignoring the statues until "something happens" is asking them to act against their own motivations as adventurers who face danger and magic as a matter of habit.
When you lay down a map of a seemingly random part of the forest trail, the players usually think "this must be important, let's search around / prepare for battle."
Much like the point above, the characters are always on alert because that is how they stay alive "in world." By laying down the map you have now indicated to the players where the story is, but, as characters you can assume that they are constantly on alert. This is not meta gaming, it is being in-character. We skip large parts of our players' journey because "nothing happens" but, I never assume that my players are just strolling without a care in the world.
Travel through a Roleplay universe is made cautiously, carefully, always on the look out. If it wasn't we wouldn't bother asking players to roll perception rolls to see if they spot that person following them. All you have done is told your players that travel is now going to involve something, but you do that with or without a map the moment you say "after several hours of walking ..."
A useful DM tool
A simple way to stop the feel that your players are reacting to the story and not their characters is to insist on them defining patrol patterns: what is the order of the party as they move through the environment? What are they doing, how far are they from each other? Maybe get them to agree to a defined formation that is the standard if they haven't said differently. This way when the encounter starts you don't need to get them to think about how they are set up. For you, the DM, never see character prepardness as being more then simply what they would do anyway. The question out of the game is when you as a DM ask them to define what they will be doing.
You roll a 1 for a player's knowledge check and feed them inaccurate information. They saw the roll and know you're full of it.
Personally as a DM I don't ever roll for a player. They make make their own rolls, with the exception of passive perception. To get around that I just roll dice randomly all the time as a DM. But, if the roll is failed I never provide false information; I tell the player they don't know, or they don't see.
If you want to do the above, make your rolls in secret so they can't see. The same can be said for players rolling to spot a trap and rolling really low. There may be no trap there but they know if there is they haven't found it. On this I expect my players to behave accordingly, open the door anyway, step down the corridor. If they don't then I will, out of game, have a small chat with the player.
Even the most disciplined players sometimes will take advantage of "Player Knowledge" over "Character knowledge." Sometimes it's hard to even tell the difference. You know that you should switch to your frost battleaxe against that Fire Demon, but does your city-raised fighter with the intelligence of an old boot know?
In this specific issue knowing you're facing a fire demon means you probably know that he isn't going to do well against fire based attacks and maybe lets try using a cold weapon. But this situation is also the one that player are in a lose-lose on. As a DM what do you want your players to do? Do you want them to
hit the fire demon with a ton of different attacks until they "stumble" on the one that works? If the first thing they use will the DM accuse them of metagaming it, should they roll a dice to randomly decide attack by attack? Doesn't that strain credulity a bit?
Also while a players intelligence may be low, or they may not have faced this enemy in this campaign before, the world of fantasy is full of tales, stories, and history. If you compare it to the ancient world the ancient Greeks told stories by word of mouth yet, I imagine they all knew how to solve the riddle of the Sphinx. It is perfectly acceptable to believe that one of the characters has some knowledge of a fire-based being and what its weaknesses might be. They might remember that famous fairytale where a prince killed a fire creature with cold, or might have been sat in an inn while an adventurer regaled them with stories about a fight they had in the fire realm. As a real person I am full of bits of information I have picked up over the years, stories I have heard. It is perfectly reasonable to accept that your characters know more then you expect them to without asking them to explain how they know this thing. Remember most characters have had a life before this campaign, for some races that life may have been many decades long.
What strategies are there to discourage the use of player knowledge, and how can you cut back on perceptions that players have of the genre itself?
In conclusion I don't think you should. This is a step toward adversarial GMing.
Players characters are not wide-eyed and new to the world; they have not been created just seconds ago (unless you're playing Paranoia but then all your problems go away). Their knowledge and ability goes beyond a simple dice roll or stat. The most stupid character in the game can have experience to draw upon, or the ability to foresee that something might be about to happen.
Anyway: do the examples presented here really break the game or affect enjoyment?
They might make a DM work a little harder, or think a bit more sneakily, but that is never a bad thing. Now if a player out of character realises that person x is the bad guy and just kills them with no in game evidence, that is a problem that needs discussion but none of the examples you provided above, in my experience, are.