Based on the following 2 links we need some form of choice
to prove Urysohn's lemma:
http://www.emis.de/journals/CMUC/pdf/cmuc9703/herrli.pdf
http://cs.nyu.edu/pipermail/fom/2007-August/011825.html
This leads me to wonder, if we assume ZF + "Urysohn's lemma"
can we derive countable choice or dependent choice?