Frist a correction - Netbackup clients can't connect to the master via the media. They must be able to connect to the master server direct. This will change in the further, but for now that is the rule of thumb.
As of now, you will have to deploy client inside each VM, Netbackup can't perform any KVM based snapshots yet. The question of deployment of media server into each tenant or not is really down to network infrastructure. Personally I would have both master and media servers in a separate zone, protected with router and access list in order to get the bandwidth required - firewall is no good. Having dedicated media servers at each tenant, limit the utilization of resources. E.g Media server at tenant A if fully loaded and backup does make the backup windows, but tenants media server C-E does is idle, but can't be used. By having all media servers in one zone you can utilize them across tenets.
There is one major vendor of backup software that support hypervisor based snapshot backup KVM - and no it not Veritas, its C.......