It's straightforward (if messy) to calculate two rationals exactly, then approximate √5 to within certain error bounds.

I wrote some code which does this, just as an experiment... and it's unbearably slow. Just try it.

  import Control.Arrow
  import Data.Ratio

  newtype Matrix2 a = Matrix2 (a, a, a, a) deriving (Show, Eq)
  instance (Num a) => Num (Matrix2 a) where
      Matrix2 (a, b, c, d) * Matrix2 (e, f, g, h) =
          Matrix2 (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h)
      fromInteger x = let y = fromInteger x in Matrix2 (y, 0, 0, y)
  fib n = let Matrix2 (_, x, _, _) = Matrix2 (1, 1, 1, 0) ^ n in x

  binom n =
      scanl (\a (b, c)-> a*b `div` c) 1 $
      takeWhile ((/=) 0 . fst) $ iterate (pred *** succ) (n, 1)
  evens (x:_:xs) = x : evens xs
  evens xs = xs
  odds (_:x:xs) = x : odds xs
  odds _ = []
  iterate' f x = x : (iterate f $! f x)
  powers b = iterate (b *) 1
  esqrt e n = x where
      (_, x):_ = dropWhile ((<=) e . abs . uncurry (-)) $ zip trials (tail trials)
      trials = iterate (\x -> (x + n / x) / 2) n
  fib' n = (a, b) where
      d = 2 ^ n
      a = sum (zipWith (*) (odds $ binom n) (powers 5)) % d
      b = sum (zipWith (*) (evens $ binom n) (powers 5)) % d
  fib2 n = numerator r `div` denominator r where
      (a, b) = fib' n
      l = lcm (denominator a) (denominator a)
      r = a + esqrt (1 % l) (b * b / 5) + 1 % 2