I'm not a fan of doubling up, but only because it makes the results really hard to measure. If you implement both, you won't know which one worked, ultimately. I'm not sure it's actually harmful - it just can be hard to track.

If you're just trying to prevent future problems (and don't have any immediate issues), I'd probably pick one and give it a few weeks.

A couple of options here. First off, though, there's really no rel="noindex" at the link level. You can "nofollow" a link, and that generally disrupts indexing, but it's not guaranteed. You're right that it can look like PR sculpting, although that's not a huge issue if your usage makes sense. In other words, if you're using rel=nofollow to keep the crawlers away from content with low search value, I generally think that's ok.

You could META noindex, nofollow the target pages, although then Google has to crawl those. The advantage is that I find the META Robots approach to be a bit more powerful.

The other option is to use parameter handling in Google Webmaster Tools (Bing has a similar function) to tell Google to ignore the "?filter" parameter. The purist in me doesn't love the engine-specific approach, but it's easier, you don't need to change the site itself, and it typically works fairly well.