The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.
The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.
One way to decide if a graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.