It existed during Gen 5
Born out of Antar's mild curiosity, PU is the least "other-y" of all of the Other Metagames. It's simply a tier created beneath NU, determined by the typical tiering cutoff of about 3.41%. It's a rather turbulent metagame, since many of the most dominant PU Pokémon are quite viable in NU, and the border between NU and PU is constantly shifting every tier shift. The fact that PU constantly changes with the rise and fall in usage of different Pokémon sets it apart from other obscure metagames.
That was part of an article in The Smog Issue 28 which was released on the 23rd of June, 2013 - well before Gen 6 came out.
Smog Issue 28
There is also a thread here relating to the idea of the PU Tier during May 19, 2012