What is the right solution (and map projection) to compute distances between points located all over the World?

If you're only concerned with calculating distances between two points on the Earth's surface, you don't really need to work this out through maps and map projections.

What you need is a formula for calculating geographical distances: http://en.wikipedia.org/wiki/Geographical_distance

If you need high accuracy, look for http://en.wikipedia.org/wiki/Geographical_distance#Ellipsoidal-surface_formulae

Why try to project the data?

As mentioned in other answers there is mathematics to calculate distances on the speriod (I guess there is in ArcGIS too).

In PostGIS you have two choices. Use the geography data type and you can use all those functions (chapter 8.3). Note the ST_Distance function working against geography type. Your other option is to use the geometry type and use the special ST_Distance_Sphere or ST_Distance_Spheroid function.

/Nicklas

Check out Haversine's formula. If you Google around a bit, you can find implementations in several languages (Javascript,C#,Python...etc).