If you just want to avoid the singletons you could create instances of every game state you need in your initialization code. Then add these to a map inside the CGameEngine class - for example:
game.AddGameState("Intro", new CIntroState());
game.AddGameState("Menu", new CMenuState());
You could than add a method to the CGameEngine to retrieve the game state instances:
GameState* GetGameState(std::string stateName);
GameState* introState = game.GetGameState("Intro");
and you could use these with the existing methods to change the states however you like.
You just have to take care of releasing the memory of all the allocated states in the deinitialization code of your game.
The downside of this approach (and the singleton approach in the linked article) is that all game state instances are residing in memory for the whole duration of the game. But this might not be a problem depending on your requirements and target platform.