I know that you can download a list of all domain names registered in
.COM/.NET but I don't think that you can do that for .co.uk domains.
Currently there are roughly 4mil, would anyone have a solution of how
to get that list of domains.

I could be wrong, but it appears that this is not as easy as it
sounds. Lists of .com, .net, and .org domain names are not difficult
to obtain, but the registry for .co.uk domains is not cooperative in
efforts to compile lists:

"A) It's not possible to download a list of all domains from Nominet,
and therefore it's impossible to find out which domains are being
expired/deleted each day since there's no raw material to 'compare'
(how would the person compiling the list know that fgjjss45.co.uk -
fictional example - was a registered domain without having access to a
list of all domains?)

B) Nominet (.co.uk oversight body) is very zealous and aggressive
about protecting their intellectual property and they have
aggressively come down on the (very) few sites that have tried to
manually produce such lists and in every single case have successfully
persuaded them to stop offering them."

http://www.webmasterworld.com/forum25/1649.htm