Would putting allerede first put emphasis on it? As in:

Han er allerede her = He is ALREADY here / He is here ALREADY Han er her allerede = He is already HERE / He is HERE already