Negative time value of put option I am analyzing valuation of European put options in non-Gaussian environment. 

I realized, that put option can easily get negative time value, when it is deep in the money (spot price close to zero). Ultimate proof, that such negative time value exists is at limit, when spot price approaches zero. Then the option value is less, than strike as the price of the underlying can move in only one direction. 

This issue (negative time value of a put) has been discussed in these pages also and opinions vary: some think negative time value is not possible, but I believe my counter-example above shows, that negative time value does exist. It is not that relevant in the Gaussian world, but can become an issue with fat tails. 

This negative time value leads to a paradox: when I apply put-call parity for a put with negative time value, I get negative valuation for a call. This should be impossible, as call option holder does not have, by definition, any liabilities and therefore value must be >=0. 

So, what explains this contradiction: is it so, that put-call parity only applies, when underlying return is Gaussian distributed?
You won't get any contradiction from the put call parity. On the contrary, I think the put call parity is very helpful in illustrating how puts can have negative time value.

First, we need a little confirmation on the terminology: I assume in your definitions the value of a derivative (its current price) equals its intrinsic value (what I could get if I exercised it now) plus its time value.

Then take a look at the put call parity $p_t = c_t - f_t$ in which $f_t$ is the value of a notional forward contract that has the same maturity and strike as the call and put in question. For simplicity let's assume the world follows Black Scholes assumptions (strike that, we actually don't need BL or any other model assumptions to make the following valuation of forward hold, apart from a constant risk free rate $r$), so that $f_t = S_t - Ke^{-r\tau}$ ($\tau$=time to maturity, or $T-t$). Hence
$$p_t = \color{blue}{c_t + Ke^{-r\tau} - K} + \color{red}{(K-S_t)}$$
The red part is apparently the intrinsic value, which makes the blue part the time value. Then you can see clearly that there is no guarantee that the blue part is greater than zero. Specifically, for example, it can easily drop below zero in the following two scenarios:

1). When the put is deep in the money, or equivalently when the call is out of the money. In this case $c_t\approx 0$, and $Ke^{-r\tau} - K &lt;0$. So it's very likely they sum to a negative value.

2). When the interest rate is high or time to maturity is long. In this case $Ke^{-\tau}$ will be small and dominated by $-K$. If $c_t$ is also significantly smaller than $K$ (which happens easily when, say, $K$ is large). 

The intuition is that if you were a put holder you'd want to get paid as early as possible because early payment means larger time value of money, but the put contract stipulates that you cannot get paid prior to maturity, which entails a loss from such deferral of cash flow. This is opposite to the call, in which case you as the call holder would want to defer the payment as much as possible and the call contract actually entitles you to such deferral of payment, which means a gain in time value.
The time value can't be negative. 

A positive time value reflects the possibility that the price of the stock might wander in such a way as to make the option in the money at expiration. Then the option gives the holder the right to exercise the option, and a make a profit.

A negative time value would reflect the possibility that the price of the stock might wander in such a way as to make the option out of the money at expiration. However, since the option gives the holder the right to exercise the option, but not the obligation, this only results in the option being worthless. So the time value can not be negative.