Efficient way to generate random planar cubic bipartite graphs
Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in:


Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), 1997.


Schaeffer describes how to efficiently generate (rooted) Eulerian planar maps uniformly at random using a bijection with a certain family of trees. In turn, Eulerian maps have a simple bijection with bi(partite-)cubic maps: see the second bullet point on slide 5 of this talk by Éric Fusy.

(Generating a uniformly random rooted planar bicubic map and then throwing away the rooting + embedding would give you a non-uniform distribution on planar bicubic graphs, but depending on what you have in mind that might be okay?)