In windows, I used to use a text editor called crimson editor which featured the best column-mode editing support I have yet to use.
When enabled via a simple Alt-C shortcut, selections could be made with the mouse or cursor keys and they would be visual blocks rather than wrapped-lines.
These selections could be deleted, moved, copied, pasted, and all of the operations just made sense. You could also just start typing, and you'd get a column of the characters as you're typing.
There are multiple ways of getting parts of the these features working separately discussed on this forum thread, but no one has yet to provide a solution that provides this all-encompassing and easy-to-use method.
If someone could point me to a gedit plugin where this work is actively being pursued, perhaps I could help with the coding myself. If someone is aware of a text editor that already provides this full functionality, I'd appreciate the info. Running crimson editor through wine and the close-but-not-quite multi-edit plugin for gedit are the temporary solutions I'm 'getting by with' for the time being.
UPDATE (2012-11): I'm now a very happy user of sublime text. It supports excellent column-mode editing and works on all three major OS platforms without any issue. Highly recommended!