Little late on this, but I wanted to chime in. The first 3 Scott Pilgram volumes may predate No More Heroes, but they don't predate the spiritual precursor to that game, Grasshopper Studio's similarly toned "Killer 7" in which you play as 7 deadly assassins (sound familiar?).
http://en.wikipedia.org/wiki/Killer7

Furthermore, the movie was made before the books were finished, and the end of the movie (where Scott starts using a sword and loads of suited goons are bursting as he slices them), which really, really feels like it was torn right out of NMH is very different from the book. So to say that what your seeing when you go to the movie wasn't inspired by NMH isn't necessarily true.
I find it really weird that such a mainstream movie would have taken so much inspiration from a few realitively unknown videogames, but man, when I was watching it that was all I was thinking.
edit: Just checked my math on this. The very first volume of Scott Pilgrim does actually predate even Killer 7, meaning the similiarities between the two were at first coincidence. I gotta think as the series went on (and when the movie was made) inspiration was pulled from the games. The final volume didn't come out until just before the movie was released.