YC has a lot of founders from outside of the US. There were four teams from outside of the US in our YC class, two from Canada, one from the UK and one team from Austria. I can think of at least four other teams from abroad from previous classes.
In fact there is a kind of UK YC inside YC. The UK guys really stick together and help each other out. If you can get a hold of any of them I'm sure they'll point you in the right direction.
Papers and immigration are always a difficult issue. In most cases you can get a work visa or whatever visa lets you attend conferences in the US and it will be enough for the 3 month YC session.