I signed up just to post this.
I have been thinking about this puzzle a lot, and have taken a bunch of notes on it. I want to share them with others to see if I overlooked anything, and just to provide a nice overview of possible solutions to the puzzle, why they don't work, and what it would take to make them work. A lot of this information can already be found throughout the thread.
The Puzzle as I Understand It
Find a Pokemon that can hit any Pokemon super effectively by using a combination of three moves (or fewer) in a 1v1 battle.
Any Pokemon is taken to mean any species of Pokemon, using any of its available abilities (this part was clarified by the person who made up the puzzle) and any legal combination of its moves (this part was not, but I would assume it since all possible abilities are to be taken into account).
1v1 is taken to mean that there will not be any other Pokemon in having any effect on the battle. Nothing will change the enemy Pokemon's ability, for example, or set up any terrain effects of weathers or anything else that might change the situation. Pokemon will also not switch out.
The opponent will not be carrying an item, which removes Arceus formes and Mega Pokemon.
From this it already follows that Skill Swap Protean is no solution to the puzzle, as it can't be assumed that a Pokemon will carry a certain type of move.
Below are some routes to solve the puzzle I have looked at, what you need to take into account for them, and some notes on specific unsuccessful solutions I have tried. When I say "hit", I mean super effectively hit.
Soak
You will need to...
-Hit Water immune 'mons
-Hit Magic Bounce 'mons (Xatu, Espeon)
Edit: -Hit Arceus
A few things of note:
Xatu and Espeon can both be hit by Dark and Ghost, so if you can hit all Water immune 'mons in two moves (one of which is Soak), this puzzle is solved by adding a Dark or Ghost move.
There is no type that hits all water immune 'mons by itself, so the above situation is impossible.
Of the Water-immune 'mons, only Cradily, Maractus, Gastrodon, Lanturn, Quagsire, Cactrune, Seismitoad, Parasect, Jynx, Toxicroak and Heliolisk (and their pre-evos, I will leave out this part in the future) cannot be hit by Electric type moves.
Only Mantine, Cacturne, Maractus, Paras, Jynx, Toxicroak, Heliolisk and Cradily cannot be hit by Grass type moves.
Only Cacturne, Maractus, Parasect, Jynx, Toxicroak and Cradily cannot be hit by a combination of Grass and Electric.
If an Electric type move is used as the first attacking move with Soak, Grass coverage will be needed to hit Gastrodon and Seismitoad, as it is their only weakness. As can be seen above, that misses a few water immune mons and Espeon.
If a Grass type move, but no Electric type move is used, Toxicroak and Cradily share no weaknesses, so no single move will cover both of them.
The only other move that hits water super effective is Freeze-Dry, but the combination of Soak and Freeze-Dry is illegal on all Pokemon.
Octillery gets Soak, Entrainment and Charge Beam, which allows it to hit all Water immune mons, but misses out on Espeon (which it could hit with Signal Beam if it wanted to; Perfect SE coverage in 4 moves, Octillery for S rank!). Espeon could Skill Swap away its own Magic Bounce, if "any combination of moves is possible" was not specified, though, so if Protean counts as a solution, this counts as well.
Tricking a Ring Target on Water immune or Magic Bounce 'mons does nothing, since it only affects immunities gained through typing, not immunities gained through abilities.
As far as I can tell, only Skill Swap removes Magic Bounce, and only Mold Breaker and its clones ignore it. Gastro Acid, Simple Beam, Worry Seed and Entrainment are reflected. Only Basculin gets Mold Breaker Soak, but it gets no moves with which it could hit a Water type.
Edit: In addition to everything above, Arceus is unaffacted by Soak because of Multitype. This means that a Soak set that is to solve this Puzzle must include a Fighting type move, which is Arceus only natural weakness. A set of Mold Breaker, Soak, a Grass or Electric Move and a Fighting move fulfills all those criteria in theory, but is illegal on all Pokemon.
Forrest's Curse
You will need to...
-Hit Grass plus any existing combination of types
-Hit the Magic Bounce 'mons
Only Trevenant gets this move, so there are a lot fewer possibilities here.
When can a move hit a 'mon after Grass Type is added? Only if the 'mon didn't resist moves Grass is weak to before.
So, any Pokemon without a resist to Fire, Bug, Ice, Poison or Flying gets hit.
Of those types, Trevenant has access to Posion in Poison Jab, Bug in X-Scissor and Ice in Nature Power in the snow.
Steel resist all three of these types, so if you use two of them together with Forrest's Curse, you will not be able to hit any Steel types.
Trevenant gets Ground and Fighting type attacks to hit Steel types.
Neither of those hit Skarmory, so if you want to hit it you have to go with Ice as your other attacking type.
Ice and Fighting gets blocked by Tentacruel among others.
Ice and Ground gets blocked by Surskit among others.
So as far as I can tell, Trevenant can't get perfect coverage in three moves.
Trick-or-Treat
You will need to...
-Hit Ghost plus any existing combination of types
-Hit the Magic Bounce 'mons
Only Gourgeist gets this move.
Already, this seems more promising from the start, as you can hit Espeon and Xatu with the Dark or Ghost move you use to hit everything that Trick-or-Treat works on.
Assuming Ghost is chosen as the first attacking type:
There are two main problems here. You will want to be able to hit Dark and Normal types. Normal types are immune to Ghost type moves, so even after Trick-or-Treat your Ghost attack will not hit them.
Gourgeist gets Fighting type coverage in Focus Blast, which gives unresisted neutral coverage. However, Spiritomb still can't be hit, as it already is Ghost type it's not possible to give it an extra weakness with Trick-or-Treat. I believe a set of Trick-or-Treat, Trick, a Ghost move and a Fighting move with a Ring Target should be able to hit everything.
It would be possible to hit Normal types after Trick-or-Treat by tricking them a Ring Target. But that means that Dark types still can't be hit.
Assuming Dark as the first attacking type:
Now it is necessary to find a way to hit Dark, Fairy and Fighting types. Fighting coverage runs into the same problem as before, Spiritomb still can't be hit.
The only other option to hit Dark types that Gourgeist gets is Nature Power in misty terrain, which is a Fairy move. This comes close to perfect neutral coverage and notably hits Spiritomb, but misses out on Mawile and Klefki, who resist both Dark and Fairy.
Adding a Fire move would, again, provide perfect coverage.
I might be missing something here, but I believe Gourgeist is also unable to hit all 'mons.
Skill Swap Colour Change
You will need to...
-Hit Arceus
-Hit Aegislash
-Hit Shedinja
-Hit Zoroark
Only Kecleon can do this.
The above four Pokemon can't have their Abilities Skill Swapped (although I am unsure if Zoroark can be Skill Swapped after being hit; it makes no difference, however).
Fighting hits Arceus and Zoroark.
Ghost, Fire and Dark hit Aegislash and Shedinja.
As far as I can tell, Fighting will be necessary, since you can't hit Arceus in any other way. This means it is necessary to have another move that can hit Aegislash and Shedinja.
If a Dark type move is used, Spiritomb can't be hit, as it is already Dark type and won't change to pure Dark through Colour Change.
Same for Ghost type moves. Fire hits Spiritomb, but not SE. It can't be exploited with Colour Change and Fighting alone.
A set of Skill Swap, a Dark move, a Fighting move, and a Fire move would be able to hit everything.
Tricking a Ring Target to Ghosts would make it possible for them to be hit by Fighting type moves, but if a moveset of Skill Swap, Trick, Fighting Type move with Ring Target is used, it's still impossible to hit most Pokemon, since Fighting can't exploit Colour Change on its own.
A set of Skill Swap, a Dark move, a Fighting move, and Trick with Ring Target would be able to hit everything, I believe.
It is important to note that it is not necessary to hit Spiritomb super effectively, only be able to hit it at all and make it change type.
However, to solve this puzzle, the type used to hit Spiritomb must either be SE against fighting, have Fighting be SE against it, or be SE against itself, since there are only two moves left after using Skill Swap.
SE against itself
Ghost was already discussed.
Kecleon does not get Dragon moves.
SE against Fighting
Flying and Psychic can't hit Aegislash.
Kecleon does not get Fairy moves.
Fighting SE against
Dark was already discussed.
Normal, Ice, Rock and Steel can't hit Aegislash.
So there is no possible type that hits all 'mons we need to hit together with a Fighting move.
So where does that leave us?
I believe that Skill Swap Colour Change is proven not to work, by exhaustion. No set of Skill Swap, Fighting Move, Second Attacking Move hits all four 'mons above and Spiritomb. It might be possible if Fighting is not needed after all, somehow.
I also think Forrest's Curse is proven not to work, since Trevenant just does not have the movepool to do it. If there is a combination of two attacking types that gets perfect neutral coverage, and hits all Grass type super effectively, that combination would solve the puzzle, I believe, but Trevenant does not get it if it exists.
In a similar way, Trick-or-Treat does not seem to work. A type combination that gets perfect neutral coverage in two attacks and hits all Ghost types super effectively would make this work, like Scrappy Fighting/Ghost.
At this point, Soak seems like the best bet, if there is a way to remove Magic Bounce that a Pokemon with Soak gets.
Basculin comes so close, but falls just short.
There is also the possibility that I missed another way to make it possible to hit enemies super effectively, but I can't at the moment see any way other than to change the opponents typing, for which I believe I exhausted all options.