It's hard for me to imagine that there is a more obvious or annoying gap in the basic feature set of Windows Phone than the lack of Undo/Redo when typing. It causes me a moment of something between mild annoyance and utter hatred on a daily basis. I miss it even more with Windows Phone 8.1 than I did with Windows Phone 8, because I find it so much more difficult to avoid fat-fingering while typing in Windows 8.1.
If there is some process for the WP to proactively check with the community of users about the desireability of new features, could I humbly suggest that use that for this one? :I would be very surprised to see it come up anywhere but in the very highest place.
Shake would be ok, I suppose, but I would prefer there to be a small icon on the same row as the "paste" icon (which appears whenever the keyboard is visible). Since the "undo" action should be visible and active more often than any other action in the copy-paste-cut-.... family ("undo" need to be available after the first keystroke -- only the keys of the keyboard itself need to be available more often), I think the "undo" button should be either at the beginning or the end of the row. You might even consider putting it at the "far" end of the row on which the paste button sits - so that it always appears in the same place on the keyboard.)
--with thanks,