Att måla på klinkers är troligen den sämsta metoden, möjligen med epoxifärg av liknande typ som används i publika källare, verkstäder osv.
Att bila bort bef. klinker är inte något jättte jobb. Köp en billig borrhammare med bilningsfunktion. Hyr sedan ev en sanerfräs med dammsugare (dammar mindre än bara en slipmaskin), och fräs bort ev klinker/fix rester. Jag tror, men har ingen egen erfarenhet att du med den maskinen även kan fräsa ner 5 - 10mm i betongen och få plats med elslingor, om bygghöjden är kritisk. Du kan även välja tunnare klinker.