Choosing a random edge with restrictions Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|U|}$ ,or $v \in V$ w.p $\frac{1}{|V|}$.
2. There exists a polynomial time oracle, which can, given $u \in U$ (or $v \in V$), returns the degree of $u$ (the degree may be exponential in $n$).
3. The size of $E$ is unknown.
4. One can not test, given $u$ and $v$, if there is an edge between $u$ and $v$.
5. There is an oracle which can, given $u$, return $v$ such that $v$ uniformly chosen from the set of all neighbors of $u$.

If one has only polynomial time (in $n$) - is it possible to choose an edge uniformly at random? Is it possible to choose from a distribution close to uniform? 

Without these restrictions, it would have been possible to choose $u$ w.p $\frac{deg(u)}{\sum deg(u)}$, and then choose $v$ u.a.r from the neighbors of $u$.
You can't.  Consider the bipartite graph with a single edge $(u_0,v_0)$, with $u_0,v_0$ randomly chosen at time of creation of the graph.  Then sampling from $U$ has only a $1/2^n$ chance to hit $u_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u_0$ or $v_0$.  Without sampling either $u_0$ or $v_0$ you have no hope of outputting the edge $(u_0,v_0)$.  So after polynomially many samples, there's only an exponentially small chance of outputting that edge.  Yet a correct algorithm must always output that edge every time.  So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.