Proper DOM parsing does seem to be the way to go (the document has structure, use it).
I hope your document has some element that encloses exactly those paragraphs and blockquotes you want to insert between, because that would make it easier to use XPath to locate that element.
Once you have that element you can iterate through its list of children. As you go through the list, count each <p> and <blockquote> element as you reach it. Whenever you pass a spot where you want an ad to be inserted, use the following node's insertBefore() method to insert the ad in before it (you'll need to build a proper DOMElement for each ad to do this).