Since Riot announced many changes, and I have been able to look at the changes on the PBE server, I thought I could share my ideas of how to play splitpush Shen or even jungle shen in season three. But everything will be explained later.

As I am not able to use the new masteries here, and the masteries being pretty standart with Shen, I think I don't have to say so much to that. I recommend building about the same with the season 3 masteries.
The runes as well as the items may seem a little bit odd to you. But I can tell you why I use these runes.

Greater Quintessence of Fortitude: These runes give Shen 26 Health each, so if you have three of these runes they give you 78 hp on lvl 1. I suppose this to be really good with Shen, as the passive of his q-skill scales with hp, so the more hp he has, the more hp he gets back, while the vaporal blade is on an enemy. This causes Shen to lose almost no health while jungling.

Greater Mark of Alacrity: I use these runes out of three simple reasons. The first reason is, that it causes your passive to trigger faster, as the cooldown gets reduced every autohit. The second reason is, that it also applies on the q's passive. So you lose even less hp while jungling. Last but not least the third reason I use these runes is, that splitpushers need alot of attackspeed.

The other runes are pretty standard, I guess. You can also take flat magic resist instead of magic resist per level, but that depends on the enemy team. But since Shen is more a lategame champ I would take the magic resist per level runes.

The starting boots and pots are standard, I guess. If you feel more comfortable with it, you can also start with the machete, but you can see that in season 3. The next item I recommend buying is kage's lucky pick. This item isn't used on jungle Shen very often. I suppose it to be good due to three reasons. The first reason is, that you need the extra money from the gold per ten effect. The second reason is, that heart of gold is getting removed at the beginning of season two, so this is the only good gold per ten item for Shen. The last reason I would buy kage's lucky pick is, that almost every ability of Shen scales with AP, so he can clear out the camps faster and because of the shield he has also got more sustain. I recommend selling kage's lucky pick after buying wit's end. But you can sell it earlier or later. If you need slots earlier and if you don't need item slots later.
Buyin Aegis of the legion gives you even more sustain while jungling, and the auro of it is really good for your team. Wit's end sunfire cape and guardian angel should be clear. You need to splitpush faster, that is made possible with these two items. Usually I would recommend buying ionic spark, but that is getting removed as well. Frozen mallet is a good item, cause the utility is pretty good, and the extra attack damage helps you with splitpushing.

The important thing about splitpushing is the map awareness and the map control. So if you want to push toplane for example, you need wards in the tribush at the baron pit, and maybe even one in your jungle. You always need to check the map if enemies are walking through your wards. And also be careful, when anyone from the enemy team is missing. Tell your team to pressure the midlane, and maybe force a teamfight, when someone is coming up to stop you. As soon as they start fighting, do your ultimate on one of the carries.

So that's it, thank you for reading it. I hope it helped you and gave you a quick look into the changes of Shen in season three.