Cram a new character into the game ASAP.
If the death occurs later in the session, I might rule that the character has to wait until the next session before they have to return (in fact, that's happened to me in the past). But it's really going to suck for that player if they show up to play, die immediately, and have to just sit through a 4 hour session.
Therefore, you should shoehorn the new character in as soon as you can. In past games, I've seen people get reintroduced almost immediately after the encounter ends, and I think that's a good balance: the missing character still impacts the encounter itself, but the player doesn't miss out on too much gameplay. Of course, if the player has to make a new character, then you should give him/her time to do that first.
Getting players to play is more important than game consistency
Obviously, both game consistency and actual gameplay are very important. However, the point of the game is to play, and forcing your players to sit on the sidelines of an entire session is a sure-fire way to make them unhappy (...from personal experience). If you can't get buy-in from your players, you can't do anything else.
In the future, have backup characters
One of my groups handles a deadly campaign by having at least one backup character. We usually make them out of mere interest and curiosity, but it's encouraged by the DM. They are obviously useful for this situation, because it allows us to jump back into the game almost immediately. Having a pre-written backup character also makes it a lot easier to integrate them into the game world, because you and your players will have had time to properly think about them.