I don't think on-page SEO is dead by any means. If you get your on-page SEO right then you can make your inbound links work much harder for you. But I've pretty much given up on dedicated SEO link building strategies. I'd much rather devote time, money and effort to good social media work and PR to generate genuine traffic - and the side effect of that is good links.
An excellent PR strategy generates far more valuable links than dedicated SEO link building work IMHO. (Even though you do have less control over anchor text).
I think the days of link building agencies is nearing the end - they were never very good anyway in my experience. Instead I think online PR agencies, well-rounded digital marketing agencies, and social media agencies (to an extent) will become the norm. SEO will about making sure your site isn't shooting your other efforts in the foot, and then consultancy to guide your other marketing and make the most of it from a link perspective.