One possibility, if the terminal supports it, is to use the terminal's Change Color escape sequence. Apparently konsole doesn't support it though. From the Xterm control sequence document (ctlseqs):
OSC Ps ; Pt BEL
Ps = 4 ; c ; spec -> Change Color Number c to the color specified by spec, i.e., a name or RGB specification as per XParseColor. Any number of c name pairs may be given. The color numbers correspond to the ANSI colors 0-7, their bright versions 8-15, and if supported, the remainder of the 88-color or 256-color table.
What this means is that the control sequence
\e]4;NUMBER;VALUE\a will change the appearance of color NUMBER. NUMBER is a color number (0–7 for the eight basic colors, 8–15 for the bright versions, and more if the terminal supports more colors). The VALUE is something that XParseColor understands, such as an RGB specification
#123456 or an X color name (look for
rgb.txt on your machine, or use
xcolors to see the possibilities).
For example, the following command changes the basic blue color (color 4) and its bright variant (4+8) to contain some green:
Note that this changes every character currently displayed in this particular color in the window. There is no way to change the meaning of a color only for subsequently displayed characters; if that's what you want, you'll have to configure each program displaying inside the terminal to use different color numbers when talking to the terminal.
Having this happen exactly when you're typing in an ssh session will be very complicated, but handling the common cases is reasonably simple: use a wrapper around ssh that changes the color palette, then runs ssh, and finally changes the color palette back. Examples of cases this won't handle are suspending the ssh process and running ssh inside screen or tmux.