One way to do it (you get it for free):
----------------------------------
1. Create a triangular mesh to cover the world sphere (for instance, start with an icosahedron, and divide every face in enough triangles to comply with your resolution requirements: 1, 10, 100, ... km^2)
2. Group the triangles in 600 (almost) equal surfaces distributed over the face of the earth ignoring population density.
3. Calculate the population behind every triangle using the available statistical data
4. Create a weighting function to evaluate how good a group is accounting for the people behind, its shape and any other parameter you like.
5. Move triangles between adjacent groups maximizing the weighting function until a maximum is reached.
6. Repeat using different initial conditions or changing the weighting function until a satisfactory solution is found.
----------------------------------
If you are interested I will implement that solution in software (including extensive documentation) and sell it to you under an Open Source license for $1500.
I am quite busy at the moment and will not be able to start working on this until mid-february... so check first with the other cheaper bidders and if they fail you can come back to me ;-)