How can convolution be a linear and invariant operation?
Your problem comes about because you're pondering the convolution of a signal by itself: $$g(x) = f(x) * f(x)$$
So, yes, if you had a block diagram where you collect f(x) from the æther and then somehow magically convolve it by itself (which can't be done physically because it would require time-reversing $f(x)$, which requires looking into the future), then yes, that would be nonlinear.
But that's not what convolution is about
Convolution is about taking an actual signal (probably what you mean by your $f(x)$), and running it through a system, who's behavior is defined by an impulse response.  An impulse response is, in a sense, a signal, but it's not an actual physical signal -- it's a full and complete description of how a linear, time-invariant system behaves in response to a signal.
Here's a fairly far-fetched analogy, that isn't coming out nearly as simple and clear as I'd like*: say you live on a farm, where goats weigh 1/3 as much as sheep, and you have a scale that reads out in goat-weights.  If you put three sheep on the scale, then the number you read is $3 * 3 = 9$.  What it looks like you have done is multiply three by three (a nonlinear operation if $3$ is a signal) and gotten 9.  What you have actually done is multiply a signal (three sheep-weights) by a fixed characteristic of a signal (one estimated-goat-weight / actual-goat-weight) and gotten an output.  Had you put four sheep on the scale, only one part of your calculation would change -- the &quot;three goats per sheep&quot; part would still be a three.
So in your original example, you're trying to convolve a signal &quot;by itself&quot;.  That doesn't happen.  You may convolve a signal by an impulse response that happens to be equal to that signal -- and even I, in a classroom setting, may tell the class that I'm &quot;convolving the signal by itself&quot;, only to have to make the above clarification.
You'll have occasion to find the autocorrelation of a signal, which looks a lot like convolution (it looks like $A_f(x) = f(x) * f(-x)$, in fact) and for which you sometimes trick a math package into doing because it doesn't have a built-in autocorrelation function.
You sometimes have occasion to find out what happens when you feed a filter with a signal that happens to match its impulse response -- but then you're feeding one distinct signal into a filter that's got eerily similar characteristics to the signal**.
You may even build a system that involves delay lines and multiplications and whatnot that &quot;convolves a signal by itself&quot; -- but then you're building a filter on the fly that gives itself an impulse response that matches a delayed version of a collected signal, and convolving.
But you never really convolve a signal by itself.
* I should never, ever, get on these boards before the caffeine has kicked in.  Yet, I regularly do.
** Well, probably quite intentionally similar characteristics, but -- caffeine.