Setup your selenium tests to use remote webdriver
For info read here - http://code.google.com/p/selenium/wiki/RemoteWebDriver and http://docs.seleniumhq.org/docs/03_webdriver.jsp#selenium-webdriver-s-drivers
UPDATE
Jeeny - "Can Jenkins do jobs on remote servers (say I find a server that doesnt need to run tests headlessly)?"
Amey - "Yes"
BUT instead of running the Jenkins job on a remote server, make your selenium tests run on a remote server.
I assume you initialize your selenium webdriver browser instance by this command
WebDriver driver = new FirefoxDriver();
change that to
driver = webdriver.Remote("http://your.remote.server:4444/wd/hub", webdriver.DesiredCapabilities.FIREFOX)