Yes, such a subgraph always exist. Let $G$ be a planar triangulation. By the $4$-colour theorem, $G$ has a $4$-colouring. We let $H$ be the subgraph consisting of all edges with endpoints coloured $1$ and $2$, or with endpoints coloured $3$ and $4$. Since every face of $G$ is a triangle, every face must contain a $12$ edge or a $34$ edge, as required. Also, $H$ is clearly bipartite since $(X,Y)$ is a bipartition of $H$ where $X$ is the set of vertices coloured $1$ or $3$ and $Y$ is the set of vertices coloured $2$ or $4$.
Regarding the algorithmic question, there is a quadratic algorithm to find such a subgraph. This follows from this paper of Robertson, Sanders, Seymour, and Thomas, where they present a quadratic algorithm to $4$-colour planar graphs.