Would it be possible to change the p2p protocol used by the bitcoin-clients without a hard-fork?
Yes, the p2p protocol itself is not consensus-critical. Of course there can not be two completely seperate networks, so you will have to take care to create bridges between the two. But other than that you could make a sneakernet p2p network where people exchange USB sticks if you like.