The other option is go on that working holiday and stay long enough to marry a native.
I got my US green card a couple of months ago on that basis, despite living/working here illegally. US immigration is about as tough as it gets, and I'd certainly recomend a friendlier country.
Of course, as an Englishman, I can't really call the US unfriendly...