That'd be a little different, but I think it'd be cool. I know what you mean, it sucks when you just finish a bout of advanced melee, only to get blasted by someone who was waiting just far enough away with a beam. There has to be a bit more planning to the idea, though.
If it were implemented as purely random, you'd probably wind up teleporting into solid map geometry half of the time. So, I see the best way to do it as adding special entities to maps, which the engine would randomly cycle you through during melee.
This would mean a little extra work for mappers, and recompiling of old maps to add the entities, but it would probably be best as a toggle-able feature anyway. That way, if it was set to be enabled on a map that didn't have the feature, it would default to off.