Cfxtrjtrk

You can get this with the combined use of the programs
xdotool
(click to install) and
xsel
(click to install).

xdotool can simulate typing into a window; xsel outputs the
contents of the PRIMARY selection (by default); the following shell
one liner will do the trick:

 xdotool type `xsel`

To bind this to any key using the System->Preferences->Keyboard
shortcuts menu item it is necessary to wrap it in a shell invocation:

 sh -c 'xdotool type --clearmodifiers -- "`xsel`"'

Typing in xdotool will not work with some programs; see the notes in
the xdotool documentation.

I was looking for an answer for this very same question, and I found this answer that says that Shift+Insert is working to paste the primary selection. I works for me. Simpler.

Calling xdotool click --clearmodifiers 2 simulates clicking middle mouse button. This works much better than using xsel (at least for me). Altough you have to position your mouse before typing...

Another xdotool suggestion, working in Debian Jessie 8.7 (Jan 2017):

xdotool click --delay 0 --clearmodifiers 2

• xdotool handles multi-byte strings (p.e. UTF-8), unlike xvkbd.


• 
  xdotool click simulates an actual click, so you don't have to click yourself to paste at mouse position, as you would have if you used xdotool type, or xvkbd.

The only problem is that --clearmodifiers will "press" back any modifier (Ctrl/Alt/Shift/Meta) you use after simulating the click. Even with --delay 0 (instead of 12ms), the command takes a little to execute. If you release the keys before it ends, your modifiers will be "pressed" again, and stuck there until you press and release the actual key once more.

So with this you have to be a bit "slow" (50ms?) to release your modifiers, if you're using any.

You can test this by setting up your keyboard shortcut, using it into a text editor, and then pressing a key (like a, or an arrow). The letter should appear in lowercase. If something else happens, you are too fast and a modifier is stuck (p.e. Shift if it's in caps, Ctrl if you selected all text, Alt if you opened a menu). Press and release your modifiers again to reset them.

If you're too fast, you can use ilkerk's suggestion:

sh -c 'sleep 0.3 && xdotool type --clearmodifiers --delay 0  "`xsel`"'

Then you have to release them in less than 300ms, and wait half a second for the text to appear.

Also, using xdotool type means you insert the text as if you where typing, at the text cursor position, and not the mouse pointer. You can change it to click if you prefer the usual middle-click behaviour.

(made this post so newcomers don't have to piece the puzzle pieces spread in the comments again)

I had the same issue and internet search didn't help me much.
The problem simulating click 2 is annoying as OP mentioned.

The problem with the above proposed xdotool and xsel is when xdotool starts "typing" you are still pressing another key. That does not always result with any output. For example if you bind it to "insert" key then xdotool is sending keys while your finger is pressing "insert" key which causes nothing.

Below is a workaround, to bind it to a key press :

sh -c 'sleep 0.3 && xdotool type --clearmodifiers --delay 0  "`xsel`"'

it is not perfect but working. now you have 0.3 seconds to finish your selection of key press (and key up).

I had problems with the solutions that simulate pasting the PRIMARY selection, so instead I added a shortcut that copies the PRIMARY selection to the CLIPBOARD. After using my shortcut I paste the CLIPBOARD in the usual way, with Ctrl+V, Ctrl+Shift+V, or Shift+Insert, depending on the application.

The command to copy the PRIMARY selection to the CLIPBOARD is

sh -c 'xsel --output --primary | xsel --input --cliboard'

which I bind to Ctrl+Insert (arbitrary choice) in the Gnome shortcut settings under System Settings -> Devices -> Keyboard

Summary of problems with other solutions: I tried the xsel | xvkbd ... and xsel | xdotool ... solutions, but found they didn't work very well because they simulate typing the PRIMARY selection character by character, which is not the same as pasting it with middle click. Problems include: there's a long delay while a large selection gets inserted one character at a time; if you want to undo the "paste", you have to undo it character by character, which is slow; if you're using "dead keys" then everything gets messed up, e.g. "pasting" "e produces ë; the xvkdb doesn't handle unicode characters correctly.