How about "C-q a"? C-q SPC already is special-cased to mean something different in isearch mode, so it wouldn't be a drastic change.
Of course that doesn't solve the problem for characters that are not represented on the user's keyboard; the quick fix that comes to mind is that quoted-insert with a negative prefix could read a character using the input method (not using read-quoted-char), then insert it as though C-q had been used with the corresponding positive prefix, so when using the TeX input method, "C-- C-q \ a l p h a" would be equivalent, during isearch, to "C-q α", to search for an alpha without an accent, breathing mark, or iota subscriptum. (The minus sign seems logical to me because we can think of C-q as a two-step command: switch to "literal mode", then read a character to insert. C-- C-q does the opposite: read a character, then go into "literal mode" to insert).
In essence, that would make C-q yet another modifier key...