A slightly longer outer cable will push the brakes up while they're not being applied. However they may still touch the tyres during braking if they would have been the right size to begin with.
Luckily yours seem slightly too short (you can see the result in the way the cable points downwards between the V-brake arms), so it would all work out. I reckon 5-10mm extra would do the trick.
Removing the rubber cover will also solve the problem, but you'll need to pay more attention to cable lubrication then.
I'd advise against using washers, as they'll alter the leverage and the balance of the brakes. Sure, you can adjust the screws near the bottom to compensate, but the braking feel will never be the same. Shame really, as these Tektro brakes really are excellent.