You are interested in the density field of an object which is a scalar valued (just a number) function over 3 dimensional region of space (shape of the object under study).
Your wish is to study this function using just 2 forms of interactions - mechanics and gravity in most simple form without destroying object.
I agree that we need to try to understand this question from very general point of view first.
Mechanics and gravity exhibit properties of superposition - which means that properties of objects spread over space are substituted with point-like properties (one example you already gave - gravitational field of a sphere does not depend on its radial density distribution - so function of density distribution is substituted with just one number of total mass).
Hence using just gravity (without scanning inside with a waves - which for gravity waves is impossible at the moment) gives a negative answer - not possible.
Same is true for mechanics because mechanics also reduces 3 dimensional distributions to point-like ones.
But! The funny part is that THAT is why mechanics and gravity are so successful theories because they allow us to abstract from inner properties of objects and reduce dynamics to only global properties.
Logically it is also clear that to know 3 dimensional distribution you need to offer algorithm which will give you that amount of information, and this information can only be obtained by means of physical interaction with each point inside of object or observation of waves emitted from each point.
Finally you already gave counterexample to your goal - the radially not uniform sphere. There is no way to find out this distribution using just mechanics and gravity without destroying it or using waves.
I'm not sure whether these theoretical ideas are is included in what you have in mind. They are only good (and the first , as far as I know, only in theory) for fundamental particles and not for measuring masses of everyday things, but here goes. The second - inference from cross coupling co-efficient between otherwise dispersionless, massless states - is actually the method we use to show that neutrinos have mass, but so far we haven't refined it enough to accurately measure that mass. Still, an inference that the rest mass is nonzero is still highly significant and counts for something IMO. Moreover, we may refine this method to give numbers in the future.
Method 1: Fundamental Particle Dispersion Relationships
This method is to infer the mass of a fundamental particle from experimentally measured dispersion relationships.
A possible fourth quality to add to your list is that mass measures what I call a fundamental particle's "stay-puttability". This is actually the generalisation $E^2 = p^2 c^2 + m_0^2 c^4$ the mass-energy equivalence you cite in disguise. (the equation is simply the pseudo-norm of the momentum 4-vector rewritten).
To look at this idea further, let's think of the Klein-Gordon equation for a lone, first quantised particle, which each spinor component of something fulfilling the Dirac equation must fulfill:
$$\left(-\hbar^2 \partial_t^2 + \hbar^2\,c^2 \nabla^2 - m_0^2\,c^4\right)\psi = 0\tag{1}$$
Hopefully you can pick out $E^2 - p^2 c^2 - m_0^2 c^4=0$ from the unwonted way I've written the equation: recall $i\hbar\partial_t$ is simply the LHS of the general Schödinger equation, so that, by the Schödinger equation, $\hat{H}$ and thus equivalent to the energy observable; also $-i\hbar\nabla$ is the momentum observable. Maxwell's equations can also be thought of as a kind of massless Dirac equation, so that the components of the potential four-vector also fulfill (1) and we can think of the photon as being included in this discussion.
For pure energy eigenstates, $i\hbar\partial_t = \hbar \omega$ and if we Fourier transform (1) into momentum space, we get from (1) the dispersion relationship for the fundamental particle:
$$\omega^2 = k^2\,c^2 +\frac{m_0^2\,c^4}{\hbar^2}\tag{2}$$
so that the group velocity is:
$$v_g = \frac{\mathrm{d}\,\omega}{\mathrm{d}\,k} = \frac{c}{\sqrt{1+\frac{m_0^2\,c^2}{\hbar^2\,k^2}}}\tag{3}$$
Massless particles must always be observed to be travelling at speed $c$, as shown by (3). They are always dispersionless. However, if $m_0$ is nonzero in (3) you can slow a particle down, or "make it stay put" by making the momentum $\hbar\,k$ very small. You can see now from (3) what I mean by mass measures a particle's "stay puttability".
So now you can in theory measure $k$ from matter diffraction experiments, or select for a narrow $k$ from a stream of particles whose mass you are trying to measure using a Bragg grating (for electrons or neutrons, read near-perfect matter crystal). Then you can presumably measure their velocities, within the bounds of the Heisenberg uncertainty principle, by using a matter version of something like a Fizeau-Foucault apparatus: i.e. a sequence of chopper wheels with angular displacements between their slits, so that only particles of a certain velocity, proportional to the chopper wheel angular speed, can make it through the chopper wheels. Then you vary the chopper speed to observe which speeds you detect particles at, and this will let you work out $v_g$. Knowing $v_g$ and $k$ now lets you work out $m_0$ from (3).
Method 2: Cross Coupling Co-efficient Measurement
This, as far as I can understand, is actually the method we use to know that neutrinos have mass. So far it is not very accurate: we can only infer nonzero mass but we haven't refined the method enough to say what that mass is. However, we may do so in the future. The beginning point of this discussion is the Dirac equation for the electron written in a particular way: we write the equations for the so-called Weyl spinors, which are a kind of circular polarisation for the electron:
$$\begin{array}{lcl}\partial\!\!\!/ \psi_L &=& -m\,\psi_R\\\partial\!\!\!/ \psi_R &=& +m\,\psi_L\end{array}\tag{4}$$
Maxwell's equations written in the same form are:
$$\begin{array}{lcl}\partial\!\!\!/ \psi_L &=& 0\\\partial\!\!\!/ \psi_R &=& 0\end{array}\tag{5}$$
That is, on comparing (4) and (5), the electron can be thought of as otherwise two massless, dispersionless particles, mutually tethered together by the cross term $m$; note the two first order equations are uncoupled in the Maxwell equation case. The first massless particle "tries" to zip off at the speed of light. Before this particle gets very far, the cross coupling term $m$ in (4) means that it changes into the other particle, which then also "tries" to zip off at lightspeed, only to be converted back to the first particle and the cycle repeats. This is the phenomenon that Schrödinger called the "Zitterbewegung" (German for quivvering motion) (can you say this word aloud without smiling? - I can't! It's a wonderful example of onomatopoeia). The nett result is that the mutually tethered system - the electron - has a rest mass: confined massless particles always have an inertia, as I discuss in my answer here.
Likewise for the neutrino. It used to be thought that the Weyl equation for the neutrino was the same as (4): three uncoupled, massless Weyl equations for the neutrino flavours. But we experimentally observe that a neutrino shifts between flavours as it propagates. Thus we know that there is a nonzero coupling co-efficient between the flavours, and therefore a mass. So flavour oscillation may in the future be another method for measuring mass.
Best Answer
The most precise measurement of the mass of an electron was reported by Sturm et al in Nature 506, 467–470 (27 February 2014), quoting a relative precision of $3\times 10^{-11}$, meaning they determined the mass to better than $3\times 10^{-41}~\rm{kg}$.
If that is not the best, at least it gives you an upper bound...
Note that if you could weigh such a small mass directly with scales on earth, the force would be equivalent to the gravitational pull of a mosquito (mass 2.5 mg) on a grain of sand (0.7 mg) at a distance of about 6 million kilometers - about 17 times the distance to the moon...
Astonishing.
Acknowledgement: CuriousOne's comment got me thinking about the measurement of the mass of the electron, and led me to the above analysis.