I've always meant to sit down and figure out some examples. OK, got it. I think the following works over any field (including finite fields and numbers fields) and so must be standard (unless I've overlooked something).
Let $E$ and $E'$ be non-isogenous elliptic curves over a field $k$ (i.e., no nonzero maps between them over $k$), and $G$ a group scheme of prime order $p$ over $k$ which occurs inside both $E$ and $E'$. Fix such embeddings. (e.g., $E$ and $E'$ over a number field with split $p$-torsion and $G = \mathbf{Z}/p\mathbf{Z}$ embedded in each.) Embed $G$ diagonally into $E \times E'$, and let $A = (E \times E')/G$.
I claim that any polarization of $A$ over $k$ has degree divisible by $p$. (Thus, this gives examples of abelian surfaces without principal polarization, and also in char. $p > 0$ examples with no separable polarization by using non-isogenous ordinary elliptic curves.) Suppose to the contrary, and let $\phi:A \rightarrow A^{\rm{t}}$ denote the symmetric isogeny that "is" such a polarization (I'm never sure if we should call $\phi$ the polarization, or be more symmetric and call $(1,\phi)^{\ast}(\mathcal{P}_A)$
on $A \times A^{\rm{t}}$ the polarization), so ${\rm{deg}}(\phi) = d^2$ where $p$ doesn't divide $d$.
Due to the definition of $A$, the map $j:E \rightarrow A$ induced via inclusion into the first factor of $E \times E'$ followed by projection has trivial kernel and so is a closed subvariety. There is also the dual map $j^{\rm{t}}:A^{\rm{t}} \rightarrow E^{\rm{t}}$, and by general theorem of polarizations the composite map
$$f:E \stackrel{j}{\rightarrow} A \stackrel{\phi}{\rightarrow} A^{\rm{t}} \stackrel{j^{\rm{t}}}{\rightarrow} E^{\rm{t}}$$
is a symmetric isogeny that "is" a polarization of $E$. In particular, it must have square degree. We likewise get a symmetric isogeny $f':E' \rightarrow {E'}^{\rm{t}}$ that
"is" a polarization of $E'$.
Consider the quotient map $q:E \times E' \rightarrow A$ which is an isogeny of degree $p$. The dual map
$$q^{\rm{t}}:A^{\rm{t}} \rightarrow (E \times E')^{\rm{t}} \simeq E^{\rm{t}} \times
{E'}^{\rm{t}}$$
is also an isogeny of the same degree, and the composite map
$$E \times E' \stackrel{q}{\rightarrow} A \stackrel{\phi}{\rightarrow} A^{\rm{t}}
\stackrel{q^{\rm{t}}}{\rightarrow} E^{\rm{t}} \times {E'}^{\rm{t}}$$
must be a direct product of a pair of maps $E \rightarrow E^{\rm{t}}$
and $E' \rightarrow {E'}^{\rm{t}}$ since $E$ and $E'$ are assumed to not be $k$-isogenous.
These maps must respectively be $f$ and $f'$ as defined above. In particular, since the degree of $\phi$ is not divisible by $p$ but the degrees of $q$ and $q^{\rm{t}}$ are each equal to $p$, and moreover each of $f$ and $f'$ has square degree, we conclude that one of $f$ or $f'$ has degree not divisible by $p$ and the other has degree divisible by $p^2$. But an elliptic curve has a unique polarization of each square degree $m^2$, namely the composite of $[m]$ with the canonical autoduality (with the right sign to get the ampleness condition). In particular, the kernel is the $m$-torsion. It follows that one of $f$ or $f'$ has kernel with trivial $p$-part, and the other has kernel containing the entire $p$-torsion.
Now $E$ and $E'$ are each naturally abelian subvarieties of $A$, and $\phi$ is an isomorphism on $p$-divisible groups (since degree is prime to $p$), so the $p$-parts of the respective kernels of $f$ and $f'$ must be where each meets the $p$-part of the kernel of $q^{\rm{t}}$. For one of $f$ or $f'$, this is the entire $p$-torsion of the corresponding elliptic curve, and in particular contains $G$. But $E$ and $E'$ in $A$ meet in exactly $G$ (scheme-theoretically) due to the construction of $A$, whence $G$ sits in both kernels. But one of the kernels has trivial $p$-part. Contradiction.