Hi David,
I agree with Rankestein that global links will definitely help you,
and one way links are good.
However I think there are other methods to build these links than talking
to so many web design companies, who will definitely be wary that they'll lose
customers to you by putting up your link, even if they are in another country.
One thing I'd like to stress is that backlinks from 'unrelated' niche will do very well
for seo, so long as you have your desired link-tag mix.
So why not do it the easier and faster way? Again 80/20 rule here.
Study your competitor and find out what they are doing:
Look at the top guy in SERP for your keyword in UK, and check his backlinks
here
Get the tips?
How about making up some free but good wordpress templates, website templates, put your backlink with the keyword there, and share them over download sites?
If you have a little budget for link building, go to those webmaster forums and buy some
blog link packages etc. This will save you a lot of time and headache.