I've actually run up against this in the past. I had a PDF file that I no longer had a copy of the original document of. The way I modified it was with Adobe's Illustrator. It is a workable solution if you have access to Illustrator, but it's a giant pain in the seat.

My document did have graphics that I had to work around - they were box labels with a logo.

Granted it's like hitting a fly with a sledgehammer, but if all else fails, it will do the job for you.

Good luck!

There is no emoticon for what I'm feeling now.