You can do this without pasting. Ctrl-Q Ctrl-J at the bash prompt inserts a newline into the command line without executing it. This is useful for multiline scripting commands.
Neither gnome-terminal nor bash link against readline. I'm pretty sure they just copied the feature; it's not that they use readline in any way.
There's lots of other programs that use C-q for quoting, for example emacs, and readline probably copied it from there in the first place.
When pasting text, it's a different code path than quoting. The terminal surely knows when text is being pasted. If nothing else, a simple heuristic based on typing speed is enough to tell apart typing and pasting.
