One point to bear in mind is that it is not typically possible to choose an open subset $U$ of Spec $A$, for a Dedekind domain $A$, so that $Cl U$ is trivial. Indeed, this is possible if and only if $Cl A$ is finitely generated. (The complement of $U$ in Spec $A$ will then be a finite set of generators of $Cl A$.)
For example, if $A$ is the affine ring of a smooth curve over $\mathbb C$ whose
completion has positive genus, e.g. $A = \mathbb C[x,y]/(y^2 - x^3 - x)$,
then $Cl A$ is infinitely generated, and so no such $U$ exists.
If $Cl A$ is finitely generated, then the problem of finding $U$ is equivalent (as you already note in your question) to the problem of finding generators for $Cl A$, and I think it is fairly standard to do this via height bounds/geometry of numbers, as in the approach via Minkowski that Qiaochu suggests.
For a related, but different, arithmetic context, one can consider the proof of the Mordell--Weil theorem and the problem of finding explicitly generators for the group of rational points on an elliptic curve or abelian varieties --- here one uses height arguments. For a geometric analogue, one can consider the Neron--Severi Theorem of the Base, about finite generation of the Neron--Severi group. In one of Lang's book, he presents a unified account of these various theorems.
Note that the connection with the Theorem of the Base is more than superficial:
if $X$ is a smooth and projective variety, then Pic $X$ will be finitely generated if and only if its connected component is trivial (so that Pic $X$ coincides with the Neron--Severi group of $X$). Then the problem of computing
a finite set of generators (which is the same as computing an open $U$ such that Pic $U$ is trivial) is the problem of making the Theorem of the Base effective for $X$. I don't know how to do this in practice, but I'd be surprised if it's easy to find $U$ just by inspection in general.
E.g. if $X$ is a K$3$ surface, then we know that Pic $X = NS(X)$, but the free rank of Pic $X$ can be as high as $20$. Is it possible just by inspection to find a $U$ inside $X$ with trivial Pic? I would guess that in practice one would use some kind of geometric analogue of a Minkowski bound to find generators for Pic $X$ --- i.e. some effective version of the Theorem of the Base --- and, having done this, one could then compute $U$ if one was so inclined. (In other words, computing Pic $X$ would come first, and computing $U$ would come second.)
I guess I can summarize this post by asking a question of my own: are there really that many $U$ for which it's easy to prove that $Cl U = 0$?