How would I abstract over borrowed bytes, files, and arbitrary readers?

Perhaps you need a GAT, or a lifetime-GAT-emulating helper trait.

trait MyReaderTrait: for<'any> MyReadOnce<'any> {}
impl<T: ?Sized> MyReaderTrait for T
where
    T: for<'any> MyReadOnce<'any>
{}

trait MyReadOnce<'r>: Seek {
    type MaybeBorrowed /* : AnyBoundsYouNeed */ ;
    fn read(&'r mut self) -> Result<Self::MaybeBorrowed, Error>;
}

In which case, the borrow-from-reader implementations can be handled separately from the same-across-lifetimes implementations, so long as you handle the former one-by-one.

trait StaticReader: MyReaderTrait {
    type NotBorrowed;
}

impl<T: ?Sized, NB> StaticReader for T
where
    T: MyReaderTrait + for<'any> MyReadOnce<'any, MaybeBorrowed = NB>
{
    type NotBorrowed = NB;
}

impl<R: ?Sized> Parser<R: StaticReader> {
    fn parse(&mut self) -> Result<Document<Self::NotBorrowed>, Error> {
        // ...
    }
}

impl<R: ?Sized + MyReaderTrait> Parser<R>
where
    R: for<'any> MyReadOnce<'any, MaybeBorrowed = &'a [u8]>
{
    fn parse(&mut self) -> Result<Document<Vec<u8>>, Error> {
        // ...
    }
}

Untested, but based around the topic of abstracting over borrowing and non-borrowing closures which comes up from time to time.