Unfortunately, there is no way to make this work using super() without changing the Base classes.  Any call to the constructors for B or C is going to try and call the next class in the Method Resolution Order, which will always be B or C instead of the A class that the B and C class constructors assume.
The alternative is to call the constructors explicitly without the use of super() in each class.
class A(object):
    def __init__(self, a):
        object.__init__()
        self.a = a
class B(A):
    def __init__(self, a, b):
        A.__init__(self, a)
        self.b = b
class C(A):
    def __init__(self, a, c):
        A.__init__(self, a)
        self.c = c
class D(B, C):
    def __init__(self, a, b, c, d):
        B.__init__(self, a, b)
        C.__init__(self, a, c)
        self.d = d 
There is still a downside here as the A constructor would be called twice, which doesn't really have much of an effect in this example, but can cause issues in more complex constructors.  You can include a check to prevent the constructor from running more than once.
class A(object):
    def __init__(self, a):
        if hasattr(self, 'a'):
            return
        # Normal constructor.
Some would call this a shortcoming of super(), and it is in some sense, but it's also just a shortcoming of multiple inheritance in general.  Diamond inheritance patterns are often prone to errors.  And a lot of the workarounds for them lead to even more confusing and error-prone code.  Sometimes, the best answer is to try and refactor your code to use less multiple inheritance.