Can mass be directly measured without measuring its weight?

Your position that mass measurement is done by measuring gravitational force is not quite correct. A balance measures the mass of an object by comparing the force of gravity on the mass in question to the force of gravity exerted on a reference mass. In some cases there is also a factor based on the geometry of the scale. The measurement is based on the set of reference masses employed. There is no need to know the value of the local $g$; the scale would give exactly the same result anywhere on earth, on the moon, or on Mars, without needing to know where it is. The only assumption is that $g$ is constant over the dimensions of the scale.

if you really need to measure inertial mass, simply put a tray on a frictionless surface. Mount springs on each side of the tray, so it bounces back and forth horizontally. Put the mass to be measured on the tray, and measure the vibrational frequency. See this video, https://www.youtube.com/watch?v=8rt3udip7l4 , for a similar real world example...

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.