My personal preference would be 919 or 912's. 919's are going to be a little harsher/harder riding and they are also slightly taller than the 912's.
Your choice, I have 912's with 33" tires and I think it is pretty perfect, but when I go to the 35" tires I will be putting 2" spacers in the rear as well, if I had the 919's I would probably just go with 1" spacers for the 35" tires oh well. Your call, win/win either way you go.
As far as needing anything else not much really. You might have to cut a very small amount of cladding for 31"+ tires but it is no biggie.