M-SPC is typically the chord Alt-Space, which activates the window menu on many systems, both X and Windows, and is consumed by the window manager before Emacs can get to it. At least that's the case on the gnome 3.8 system I'm typing this on. And I would not want to disable the binding for the window-menu as I like it's functionality and have many years of muscle memory for it. So while M-SPC seems to me an obvious variation on C-SPC, it should probably not be the primary way to access this feature.
I _do_ think that this should be easily accessible. I have fond memories of rectangular cut/copy/paste being a first class citizen in the Brief text editor that I haven't used since probably '88. So I would prefer as simple a chord (or sequence) as possible that still identifies it as being just a variation on C-SPC.
So to the extent that there is a vote, I would go for either 'M-x SPC' or 'C-SPC C-SPC', or 'C-M-SPC'.
Have you also considered, though, making rectangular regions work well at the elisp level? For example, so many commands take (point mark) from (interactive "r") and presume to think that it's a non-rectangular region. Would it be useful to have a new interactive code that instead supplies three arguments, (point mark shape) where shape is 'linear or 'rectangle.