Due to the scarcity of Nametags in the console versions I think nametags should be a rare drop from some mobs. Maybe bats or even cave spiders. Sure this makes it possible to "farm" nametags, but honestly that's not a game-breaking issue. While they're at it, 4J should add nametags to nether fortress chests as well.
Nametag Drops