**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](http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf) of Robertson, Sanders, Seymour, and Thomas, where they present a quadratic algorithm to $4$-colour planar graphs.