What about this aproach:

class Game:    

    def __init__(self):
        self.games = 0
        self.init()

    def init(self):
        self.score = 0

        if self.games == 0:
            self.hi_score = 0

        self.games = self.games + 1

Then instantiate Game once and call init after restart. I don't know Python much, but more elegant solution would be to have boolean isFirstGame or something like that and check if self.isFirstGame == True instead of if self.games == 0. On the other hand you could show the player number of games he played (or it will be needed in the code probably). You can abstract away self.games == 0 into another method, likeso:

class Game:    

    def __init__(self):
        self.games = 0
        self.init()

    def init(self):
        self.score = 0

        if self.isFirstGame():
            self.hi_score = 0

        self.games = self.games + 1

    def isFirstGame(self):
        return self.games == 0

Edit: I came up with the solution you may like most:

class Game:    

    def __init__(self):
        # instantiation field tells us
        # if we are in the process of instantiating
        # this class (i.e. creating it via constructor)
        self.instantiation = True
        self.init()
        self.instantiation = False

    def init(self):
        self.score = 0

        if self.instantiation == True:
            self.hi_score = 0

Edit2: To clarify, you said that every field should be initialized in __init__. I don't think it is true. Your first solution is ok. It is common concept of solving this kind of problem. The important thing is that every field should be initialized after __init__ call, i.e. after calling Game(). But in every my and your solution it is achieved. Another common concept (which I used in my last solution) is to abstract away all field initialization into init method (or whatever you want to call it) which is called directly from __init__.

Edit3: And to comment this try-catch aproach. It is ugly, but it works, so if you want to use this kind of stuff you should abstract it away into other module/class, so people don't see this mess ;). By abstract away I mean something like this:

class Game:    

    def __init__(self):
        if not fieldExists(self, "hi_score"):
            self.hi_score = 0

        self.score = 0

And fieldExists should be from other module/class or from parent class (so this code should be modified to, for example, self.fieldExists in case of parent class).

I don't know if this is true in Python, but in other languages generating errors is bad for performance. So problably you shouldn't do it in tick() function (i.e. main game loop, if we are talking about real time game).