Four years on, I'm in a similar situation as the OP.

It looks like DKB does charge an exchange fee for purchases now, but still not for cash withdrawals.

The only card I have found with no currency fee for purchases is this one:

http://gebuhrenfrei.com/

The page design does not inspire confidence, to say the least. Does anyone have practical experience of using this card? Online reviews focus mainly on the fact that one has to remember to pay the bill each month, which I guess just means that it works the way most credit cards outside of Germany work.