Here is another construction:

If $A$ is a $g$-dimensional principally polarized abelian variety over $\mathbf{C}$ with $\operatorname{End} A = \mathbf{Z}$, and $G$ is a finite subgroup whose order $n$ is not a $g$-th power, then $B:=A/G$ is an abelian variety that admits no principal polarization.

Proof: If $B$ had a principal polarization, its pullback to $A$, given by the composition $A \to B \to B' \to A' \simeq A$ (where $A'$ is the dual of $A$ and so on) would be an endomorphism of degree $n^2$. But this endomorphism is multiplication-by-$m$ for some integer $m$, which has degree $m^{2g}$. So $n$ would have to be a $g$-th power. $\square$

To complete this answer, observe that most abelian varieties $A$ over $\mathbf{C}$ satisfy $\operatorname{End} A=\mathbf{Z}$. An explicit example is the Jacobian of the hyperelliptic curve that is the smooth projective model of the affine curve $$y^2= a_{2g+1} x^{2g+1} + \cdots + a_1 x + a_0$$ where $a_{2g+1},\ldots,a_0 \in \mathbf{C}$ are algebraically independent over $\mathbf{Q}$.

Remarks:

1. Of course there is no reason to restrict to $\mathbf{C}$. For instance, one can find examples over $\mathbf{Q}$ by using the fact that the endomorphism ring injects into the endomorphism ring of the reduction modulo any prime of good reduction, and combining this information for several primes.

2. For an arbitrary abelian variety $A$, if you are given a polarization $A \to A'$, then if there is a principal polarization, following the first by the inverse of the second would give you an endomorphism of $A$. So one way of answering the existence question is to determine the endomorphism ring of $A$ and to study those endomorphisms that factor through your given polarization. (That's not quite sufficient, but it gives you an idea of the complexity of the problem since determining the endomorphism ring can be rather difficult.)

Here is another construction, followed by some comments on how to solve the existence problem in general.

If $A$ is a $g$-dimensional principally polarized abelian variety over $\mathbf{C}$ with $\operatorname{End} A = \mathbf{Z}$, and $G$ is a finite subgroup whose order $n$ is not a $g$-th power, then $B:=A/G$ is an abelian variety that admits no principal polarization.

Proof: If $B$ had a principal polarization, its pullback to $A$, given by the composition $A \to B \to B' \to A' \simeq A$ (where $A'$ is the dual of $A$ and so on) would be an endomorphism of degree $n^2$. But this endomorphism is multiplication-by-$m$ for some integer $m$, which has degree $m^{2g}$. So $n$ would have to be a $g$-th power. $\square$

To complete this answer, observe that most abelian varieties $A$ over $\mathbf{C}$ satisfy $\operatorname{End} A=\mathbf{Z}$. An explicit example is the Jacobian of the hyperelliptic curve that is the smooth projective model of the affine curve $$y^2= a_{2g+1} x^{2g+1} + \cdots + a_1 x + a_0$$ where $a_{2g+1},\ldots,a_0 \in \mathbf{C}$ are algebraically independent over $\mathbf{Q}$.

Remarks:

1. Of course there is no reason to restrict to $\mathbf{C}$. For instance, one can find examples over $\mathbf{Q}$ by using the fact that the endomorphism ring injects into the endomorphism ring of the reduction modulo any prime of good reduction, and combining this information for several primes.

2. For an arbitrary abelian variety $A$, if you are given a polarization $A \to A'$, then if there is a principal polarization, following the first by the inverse of the second would give you an endomorphism of $A$. So one way of answering the existence question is to determine the endomorphism ring of $A$ and to study those endomorphisms that factor through your given polarization. (That's not quite sufficient, but it gives you an idea of the complexity of the problem since determining the endomorphism ring can be rather difficult.)