Personally, I like the idea of going with an English Barleywine with super high starting gravity (1.125 or even a bit bigger). In order to pull that off, you'll need a very long boil of at least 2 hours or longer. The reason for the long boil is because you'll find that as you make bigger beers, your efficiency will likely drop from what you're used to, so a longer boil will let you sparge longer to collect more sugars. On the bright side, a long boil is beneficial to this style, so it will serve to improve the final beer.
I would also recommend including a fair amount of high quality base malt (I like Maris Otter and Golden Promise), but I also stretch this with some Gambrinus 2-row to keep the cost reasonable.
As far as fermentation goes, you'll need a whole lot of yeast. I usually will make a small beer (OG 1.040 or less) and use the entire yeast cake for the barleywine. Lately I like the Wyeast 1728 Scottish Ale yeast, and that yeast is especially convenient because a Scottish 60 makes a great starter beer. With a beer that big, you'll need a lot of oxygen, so if you have an O2 system, it will pay off. If you're shaking to aerate, you won't need to go to the gym for a few days.
Be careful not to let the fermentation get too hot. It really should stay in the 60's, otherwise you run the risk of getting some hot alcohol flavors in the final beer.
My last bit of advice is to set some bottles aside. A great barleywine can age for a really long time, so if you aren't wowed by it in the first year, give it some time and see what it does. Your patience will be rewarded.