Have Master Yi split-push against Nasus. If he built correctly, he can beat Nasus so long as he has his ultimate up with little effort (and this is coming from a Nasus player who dabbles with Master Yi occasionally).
The only reliable waveclear on their team is Zed and his requires using all of his abilities. Have Ahri clear minion waves so that you can siege, have Mundo spam his cleavers to harass the enemies down, and try to get a pick with Ahri's charm.
Also, their team composition is primarily physical damage. Shen and Mundo should have been able to stack armor and health to tank like gods.
Quite frankly, your team has a better team composition and the enemy team relied pretty much entire on snowballing to compensate for their lack of a magic damage threat, teamfighting, and siege.
The only way I really see your team composition losing to them is that you fell too far behind early for your teams to be relevant, members of your team were regularly picked out and assassinated alone, or you didn't play the matchup properly.