I'm want to do the same thing. I'm not worried about people without js though, but the facebook-js-files loads very slow and that slows down my whole site. Facebook doesn't work without js so i guess everyone who want to login with facebook on your site supports js.
But to the question. In the PHP-lib there is one method called get_login_url that you can use to get a sign-in-url for your app.
$connectUrl = $fb->get_login_url("http://www.yoursite.com/loggedin.php",0);
So you can make your own connect-button that links to that url. Once the user signed in facebook will redirect him back to the url you specify. If the user is already online on facebook he will be redirected back immediately.
What i'm still missing though is a possibility to check if a user is signed in on facebook already without forcing the user to click a login button. Havn't figured out any way to do that without javascript yet but i'll let you know if i find something.