Yes, no variable assignment is possible for an empty structure. Nevertheless it is perfectly possible to work with them. The branch of logic that does so is often called "free logic". Here "free" means "free of existential suppositions". The Stanford Encyclopedia article [1] makes a further distinction between "free" logic, in which terms may be undefined, and "inclusive" or "universally free" logic, in which an empty domain is permitted. I recommend that article as a good place to read about these logics.
As hardmath points out, the validities in free logic are not the same as usual first order logic, because e.g. $(\exists x)(x = x)$ is classically valid but not valid in free logic. There are more complicated examples; for example, $(\forall y)(\exists x)(x = x)$ is true in an empty domain, but its substitution instances are all false.
Here is the method for assigning truth values without going through variable assignments. Given a structure $M$, first extend the language by adding a new constant symbol $c_x$ for each element $x$ of the domain of $M$. Then an existential sentence is true in $M$ if and only if some substitution instance of it is true (where the quantified variable is replaced by a constant symbol). Similarly a universal statement is true if and only if every substitution instance is true. Even in classical logic I find this approach more elegant than the definition via variable assignments, but the two approaches are equivalent in that context.
1: http://plato.stanford.edu/entries/logic-free/