C-a C-SPC C-e M-w does work in all versions of Emacs. The only reason it doesn't work for you is that you've changed the key bindings. If you're using a GUI Emacs, you can use home S-end C-insert or Home S-End M-w instead. This may or may not work in a terminal, depending on how the terminal passes function keys to Emacs.
I'm can't use C-a because this ...
You're in luck; this is already built in. C-y yanks the last thing that you've killed or copied, and M-y replaces it with the next item from the kill-ring, which contains everything you've killed or copied in your current Emacs session.
This can be done by advising the function that sets the clipboard.
;; Clipboard history.
(defvar my-clipboard-history-limit 10)
(defvar my-clipboard-history--list nil)
(defun my-clipboard-history-paste (&optional index)
(insert (nth (or index 0) my-clipboard-history--list)))
(defun my-clipboard-history-paste-penultimate ()
In my case, the cause was having started Emacs as a tab of GNU Screen and connecting to it by emacsclient. After restarting Emacs from within the X2Go session, the bidirectional clipboard started working again.