I use Parcellite. It syncs clipboards, keeps a history, and works with good old Shift+Ins for pasting.

Then again - if I weren't using Parcellite, I'd use this right here. Very welcome software for Linux, I'd say. Well thought out!