It really depends on how much you trust them.
Option 1 - Keep doing it yourself
If you don't trust them at all, don't give them any access...though really, they control your firewall, so you must trust them at least somewhat. Still, nothing else will be as secure as giving them no access as all.
Option 2 - Give them a very limited account
If you trust them not to do anything malicious (but don't trust them not to do anything STUPID), give them a chrooted shell that has ping and traceroute copied to it, which they can SSH into and run tests. Depending on how well you set that up, it can be anywhere from swiss cheeze to fairly secure. But even if that's not impenetrable, it stops them from accidentally doing any harm. (I'm assuming linux here since you mentioned SSH...windows don't have a very good equivalent as far as I know).
This is fairly easy to setup, but requires the network team to login and run the commands themselves.
Option 3 - Web based traceroute
Since you mentioned that having them login to the server might have social/political problems, another option might be to setup a very simple website (or folder on an existing website if these are webservers) that has a page that will run traceroute and ping (and nothing else). Something like http://tracert.com/, but run from your own server. You could restrict it to a certain range of source IP addresses or require a username/password to get to the page if required.
If you go for that method, you may find some useful existing scripts by searching for something like "web based traceroute php", or you could write your own as long as you are careful about properly escaping the user input.
This will be simplest and fastest for them to use, and gives them very little more access than what they already have by being in control of the network.
You could even get it ready for them ahead of time - if you wanted to allow outbound traffic from your server example.com to 192.168.55.100, you could send them a ticket like:
Please change the firewall to allow us to connect to 192.168.55.100. Can you please check that it works by clicking this link and checking that we can ping it? http://example.com/networktools/ping.php?ip=192.168.55.100
Depending on the level of trust, you could also include tools like nmap so they can verify ports are accessible.