Solution 1:

This nostalgic contraption was hard to make, is not very pretty, but works.

First of all, create 3 scoreboard objectives: a death count, a player kill count and a dummy objective. Let's call them ActualDeaths, PlayerKills and Deaths:

/scoreboard objectives add AcutalDeaths stat.deaths

/scoreboard objectives add PlayerKills stat.playerKills

/scoreboard objectives add Deaths dummy

Now, onto the command blocks:

Command Blocks.

I will be referring to the command blocks on the screenshot according to the colorful blocks I assigned to them, so for example, the one on the far right is the "blue" command block (and the two command blocks on the left-most are GREEN and PURPLE, not lime and magenta).

Anyways, let's get to the commands:

The blue command block is powered by a redstone clock, and simply tests if anyone has killed a player:

/testfor @a[score_PlayerKills_min=1]

The yellow command block is powered by the same redstone clock as the blue one, and tests if anyone has died:

/testfor @a[score_ActualDeaths_min=1]

The purple command block resets the ActualDeaths scores, so that the comparators leading from the yellow command block are reset:

/scoreboard players set @a ActualDeaths 0

The red and green command blocks run their commands only if both the blue and yellow command blocks have passed their /testfor commands at once (that's why the piston is there). Here's what they do:

The red command block adds 1 Deaths scoreboard point to every player that has a score of ActualDeaths at least 1 (in other words, it gives the point to anyone that has died in the last few gametics):

/scoreboard players add @a[score_ActualDeaths_min=1] Deaths 1

The green command block resets the PlayerKills scoreboard, so that the blue command block's comparator is reset:

/scoreboard players set @a PlayerKills 0

That's it! Be aware that it may not be perfect and it might fail counting in all deaths in cases like two players dying in the same tick, since the only way I was testing this was by shooting myself to death by arrows.