You're right. $V \neq \emptyset$ is needed to avoid every set being nowhere dense...
Yes, these definitions are equivalent:
Note that for any subset $A$ of a space $X$ and any open subset $O$ of $X$ we have that $$O \cap \overline{A} \neq \emptyset \text{ iff } O \cap A \neq \emptyset$$ (right to left is trivial as $A \subseteq \overline{A}$, and if $p \in O \cap \overline{A}$ then $O$ is an open neighbourhood of $p$, so as $p \in \overline{A}$, $O$ must intersect $A$ as well.)
Now suppose $A$ obeys your definition, and we will show that $\operatorname{int}(\overline{A}) = \emptyset$. To see this, let $U$ be any non-empty open subset of $X$. Then we have we have $V \neq \emptyset$ with $V \subset U$ and $V \cap A = \emptyset$ and by the above equivalence $V \cap \overline{A} = \emptyset$. This means that $V \subseteq X\setminus \overline{A}$ and in particular that $U \nsubseteq \overline{A}$, as witnessed by any point of $V$. As $U$ was arbitrary, $\overline{A}$ contains no non-empty subset of $X$. We conclude that $\operatorname{int}(\overline{A}) = \emptyset$.
Conversely, if $\operatorname{int}(\overline{A}) = \emptyset$, let $U$ be any non-empty open subset of $X$. Then we know that $U \nsubseteq \overline{A}$ (or $U$ would be part of the (empty) interior of $\overline{A}$), implying that $V = U \cap (X\setminus \overline{A})$ is open, non-empty and a subset of $U$ that misses $\overline{A}$, hence a fortiori $A$ too. So $A$ is nowhere dense in your original definition.
As an aside: your first definition also explains the name better. A space $X$ is called nowhere $P$ (where $P$ is some property) if no non-empty open subset of $X$ has the property $P$.
E.g. we can verify that $\mathbb{Q}$ is "nowhere locally compact".
If $X$ is a $T_1$ space without isolated points is "nowhere finite".
So, analogously, a set $A$ is nowhere dense if it is not dense in any non-empty open set (and this is what the $V$ inside a $U$ witnesses: any point of $V$ is not in the closure of $A$ inside the subspace $U$ so $A$ is not dense in $U$).