Contacting university for potential PhD collaboration without the presence of my supervisor The question might be misleading, so I will explain in more details: 
The company in which I am employed offered me to do a PhD. The subject and everything else has been already approved and funded, the only thing missing is the university to make the collaboration with.

My supervisor already has some contacts and there seems to be a good feedback, my concern however is that, given the fact that in the company itself there is nobody with knowledge on the subject, I believe to be very important to have a strong academic support in order to have a reference if I stumble upon some issue. 

Without going too much into details I found the main academic centers advanced in the subject, so I was thinking to contact them in order to see if they are interested in a collaboration. The problem is that my supervisor and the chief of the group are both on holidays, they are unreachable and they will be back in a month; waiting for both of them to come back would mean losing a month in which I could have arranged a communication with the potential academic partners and furthermore the objective is to set an agreement in september in order to begin the PhD in December at most. 

I already spoke with my supervisor about this, and he said that eventually I could have looked for something independently, but this was a couple of months ago and before he found some of his contacts; my concern is that even though he is a really cool and relaxed guy I feel like overstepping him and making him seem that I do not trust him on this.

The question is therefore: should I contact the universities and see if they are interested without waiting for my supervisor to return in order to gain some time, or should I just let him take care about all this and eventually look for something together with him later?
Actually it seems wiser to go ahead and look for suitable programs and doctoral advisors. It shows initiative that would be valued in most places. You don't need to accept anything, of course. But if people are interested (or not) it is good to know that. 

I find it hard to imagine a boss who would think it improper, though I've had some pretty bad ones. 

You never know what you'll find until you look. 

Moreover, once you are in a doctoral program your work supervisor will play little part. It is your doctoral supervisor who will be your guide.