I feel like I have tried every possible free pdf solution on Ubuntu. Some seem to have great potential but at the end of the day are just too buggy or complex. These three solutions for me have passed the test of time:
I do a lot of combining of PDF documents (as in the second scenario) and I find PDF-shuffler simple and convenient. I have also used it to extract pages out of a larger pdf document and it works well there too. The PDF-shuffler GUI is simple and it works consistently.
Despite my love for PDF-shuffler, I turn to the command line when scenario two type situations get at all complicated. You can't beat pdftk for its ability to handle the basic manipulation of pdf files. And, as you'd expect, it is much faster than any GUI which becomes more critical as the files become larger. Don't be intimidated by the command line. Many of the tools for editing PDF are more difficult to figure out how to use than opening up the terminal and then using one of the examples on the pdftk site as a template to do what you want.
The truth is, there isn't a super easy way to edit pdf files following scenario A above. That is because PDF is a universal format and some of the structure of the document is lost when it is converted to PDF. A simple example: if you take a 3 page report and convert it to a PDF you have broken the links between the text on each page. If you edit the pdf version of it and delete a paragraph on the first page the text from pages 2 and 3 won't automatically flow onto the first page. It would be much easier to edit that document in the original program used to create it.
But for whatever reason, you don't have the original document so you are stuck working off of a PDF. So set your expectations appropriately when editing a PDF document following scenario A.
Once you set your expectations accordingly, you'll see that inkscape is the best tool for the job here. It will allow you to import a single page of the PDF document as an inkscape vector graphic. There will be a few things grouped together that don't really make sense, and you may have to change some fonts (assuming you don't have the original fonts installed), but really it is slick.
There is a learning curve to Inkscape but the truth is that you can't manipulate PDF without using some program with a learning curve. For my time, I'd prefer to invest that in learning Inkscape--a great application for creating vector graphics that can come in handy for lots of different scenarios--than I would in trying to figure out how to use a special tool just for editing PDFs.