Calculate normals from vertices
You are not too far off with your second averaging approach. The problem is, that the area is the wrong weighting factor for what you want to achieve. You want each of the 3 sides of the cube to contribute equally to the vertex normal, but you need to extract the information from the adjacent triangles. The area and the number of triangles are bad weighting factors since they vary with the number of triangles per side. But one thing stays always the same at each vertex: The angle between two edges at the side. So you just need to take the angle of each triangle connected to the vertex and use it as a weighting factor for its normalized face normal. The weighting factors will always sum up to 90°/$\frac{\pi}{2}$ per side of the cube. Look for example at the bottom left vertex at the front in the image you posted.

Your first approach fails because it yields:

$$N_v = \frac{2*N_l + 2 \cdot N_f + 1 \cdot N_b}{5}$$

where $N_l$ is the left, $N_f$ the front and $N_b$ the bottom side normal. Assume them to be normalized. The factors result from the triangle count at the vertex and their sum.

Your second approach fails because it yields: 

$$N_v = \frac{N_l + 0.5 \cdot N_f + 0.5 \cdot N_b}{2}$$

Here the factors result from the fact, that only the left face has all its triangles connected to the vertex. The bottom face connects only 1 of 2 and front face only 2 of 4 equally sized triangles to the vertex.

If you take the angles, you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 2 \cdot 45 \cdot N_f+ 90 \cdot N_b}{270}$$

Now each side contributes equally and independent of the number and size of triangles connected to the vertex.

EDIT:

I just realized, that the front face also contains only 2 triangles. The diagonal of the back face triangles irritated me. However, this will not affect the conclusion but the weigting factors change. For the fist approach you get:

$$N_v = \frac{2*N_l + 1 \cdot N_f + 1 \cdot N_b}{4}$$

The second remains unchanged and for the angles you get:

$$N_v = \frac{2\cdot 45 \cdot N_l + 90 \cdot N_f+ 90 \cdot N_b}{270}$$

which is still correct. What is interesting is that both your approaches give the same results for the shown cube, since a connection of the vertex to 2 triangles also means that the area weight is doubled. You can also see this if you compare both pictures.