Carolina Tailwinds (http://www.carolinatailwinds.com/) also runs Outer Banks bike trips - the northern banks tour includes Hatteras and Ocracoke - you might be able to cheat off their routes, too. I don't know Hatteras at all, but you might want to check out kayaking as another outdoor activity - there are probably kayak rentals available, with or without guides.