I can understand how it's hard to give up good players. I'm am a huge Pens fan, and in previous versions of the game had to give up a couple good players to both follow the cap limit and to get the roster that I wanted. Getting rid of Malkin was REALLY hard on me lol.
When it comes to rebuilding, you have to be open to anything. Explore your options through free agency if there is anyone there that can fit into your lineup. Also, go through and make a list of players that you want, write them down and keep a list. After that, look around for similar players that you may be able to get for a little less (such as a slightly lower overall).
Hopefully all of this makes sense. I tried to think it through as well as I could, but I'm not always the best at putting my thoughts into words.