A friend of mine was able to construct a vector $u$ such that $v-u \in U^\perp$.
Assume that $U$ is finite-dimensional and $\beta|_{U\times U}$ is non-degenerate (which of course is equivalent to $U \cap U^\perp = \{0\}$). Now for any given basis $\{u_1, \dotsc, u_m\}$ of U consider the map $\phi\colon V \to U$ given by $v \mapsto \sum_{i=1}^m \beta(v,u_i)u_i$ as in my original post. How does the kernel of this map look like? We have $v \in \ker(\phi) \Leftrightarrow 0 = \phi(v) = \sum_{i=1}^m \beta(v,u_i)u_i \Leftrightarrow \forall i\in\{1,\dotsc,m\}\colon \beta(v,u_i)=0\Leftrightarrow v \in U^\perp$ (the second right implication is true because of linear independency). So we have $\ker(\phi) = U^\perp$ and it follows for the restriction $\phi|_U$ that $\ker(\phi|_U) = \ker(\phi) \cap U = U^\perp \cap U = \{0\}$ which means that $\phi|_U$ is injective. Since $U$ is finite-dimensional, it is also bijective.
Now consider the map $\psi \colon U \to V$ given by $u \mapsto (\phi|_U)^{-1}(u)$. One can easy check the identity $\phi\circ\psi = \mathrm{id}_U$. Now let $v \in V$ be any vector, which we can write as $v = \psi\circ\phi(v) + (v - \psi\circ\phi(v))$. The first summand obviously is an element of $U$, the second one an element of $U^\perp = \ker(\phi)$ because of $\phi(v - \psi\circ\phi(v)) = \phi(v) - \phi \circ \psi \circ \phi(v) = \phi(v) - \mathrm{id}_U \circ\phi(v) = 0$.
So all in all, $\psi\circ\phi(v)$ is the vector I was searching for.

A friend of mine was able to construct a vector $u$ such that $v-u \in U^\perp$.
Assume that $U$ is finite-dimensional and $\beta|_{U\times U}$ is non-degenerate (which of course is equivalent to $U \cap U^\perp = \{0\}$). Now for any given basis $\{u_1, \dotsc, u_m\}$ of U consider the map $\phi\colon V \to U$ given by $v \mapsto \sum_{i=1}^m \beta(v,u_i)u_i$ as in my original post. How does the kernel of this map look like? We have $v \in \ker(\phi) \Leftrightarrow 0 = \phi(v) = \sum_{i=1}^m \beta(v,u_i)u_i \Leftrightarrow \forall i\in\{1,\dotsc,m\}\colon \beta(v,u_i)=0\Leftrightarrow v \in U^\perp$ (the second right implication is true because of linear independency). So we have $\ker(\phi) = U^\perp$ and it follows for the restriction $\phi|_U$ that $\ker(\phi|_U) = \ker(\phi) \cap U = U^\perp \cap U = \{0\}$ which means that $\phi|_U$ is injective. Since $U$ is finite-dimensional, it is also bijective.
Now consider the map $\psi \colon U \to V$ given by $u \mapsto (\phi|_U)^{-1}(u)$. One can easy check the identity $\phi\circ\psi = \mathrm{id}_U$ and also $\mathrm{im}(\psi) = U$. Now let $v \in V$ be any vector, which we can write as $v = \psi\circ\phi(v) + (v - \psi\circ\phi(v))$. The first summand obviously is an element of $U$, the second one an element of $U^\perp = \ker(\phi)$ because of $\phi(v - \psi\circ\phi(v)) = \phi(v) - \phi \circ \psi \circ \phi(v) = \phi(v) - \mathrm{id}_U \circ\phi(v) = 0$.
So all in all, $\psi\circ\phi(v)$ is the vector I was searching for and one does not need $V$ to be finite-dimensional.