Go for whatever is most readable and easily maintainable. Just because you can write it out in a single line doesn't mean that you should. Your existing solution is close to what I would use other than I would user iteritems to skip the value lookup, and I hate nested ifs if I can avoid them:
for key, val in d.iteritems():
if filter_string not in key:
continue
# do something
However if you realllly want something to let you iterate through a filtered dict then I would not do the two step process of building the filtered dict and then iterating through it, but instead use a generator, because what is more pythonic (and awesome) than a generator?
First we create our generator, and good design dictates that we make it abstract enough to be reusable:
# The implementation of my generator may look vaguely familiar, no?
def filter_dict(d, filter_string):
for key, val in d.iteritems():
if filter_string not in key:
continue
yield key, val
And then we can use the generator to solve your problem nice and cleanly with simple, understandable code:
for key, val in filter_dict(d, some_string):
# do something
In short: generators are awesome.