In previous games, to get rematches with trainers, you used the VS Seeker to see if the trainers were willing to battle. In HeartGold & SoulSilver however, the rematches are done a different way. Firstly, only a few dozen trainers in Kanto & Johto are capable of being battled again.

In order to get the rematch, you have to receive the PokéGear number from the trainer in question. Then, on a certain day, you will need to ring the trainer in question to organise a rematch. It is not guaranteed that a rematch will be discussed when you call but keep trying and you should get it. Below is a list of all the trainers, battleable on Tuesday, and their teams including their first team and each team's increase in level. Click the other days to go to their page

Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Tuesday

Time Location Trainer
Morning
4am-10am		 Johto - Route 35 Bug Catcher Arnie
Teams

First Battle
Bug Catcher
Arnie		 Venonat
Level 15
Second Battle
Bug Catcher
Arnie		 Venonat
Level 36
Third Battle
Bug Catcher
Arnie		 Venomoth
Level 43
Fourth Battle
Bug Catcher
Arnie		 Nincada Venomoth
Level 45 Level 56
Day
10am-8pm		 Johto - Route 43 Picnicker Tiffany
Teams

First Battle
Picnicker Tiffany Clefairy
Level 21
Second Battle
Picnicker Tiffany Clefairy
Level 36
Third Battle
Picnicker Tiffany Clefable
Level 41
Fourth Battle
Picnicker Tiffany Clefable
Level 61
Day
10am-8pm		 Johto - Shining Lighthouse - 2F Gentleman Alfred
Teams

First Battle
Gentleman Alfred Noctowl
Level 22
Second Battle
Gentleman Alfred Noctowl
Level 36
Third Battle
Gentleman Alfred Noctowl
Level 42
Fourth Battle
Gentleman Alfred Noctowl
Level 58
Night
8pm-5am		 Johto - Route 31 Bug Catcher Wade
Teams

First Battle
Bug Catcher Wade Caterpie Caterpie Weedle Caterpie
Level 2 Level 2 Level 3 Level 2
Second Battle
Bug Catcher Wade Metapod Butterfree Kakuna Metapod
Level 18 Level 29 Level 22 Level 18
Third Battle
Bug Catcher Wade Butterfree Butterfree Beedrill Butterfree
Level 28 Level 40 Level 37 Level 28
Fourth Battle
Bug Catcher Wade Butterfree Butterfree Beedrill Butterfree
Level 36 Level 52 Level 43 Level 36
Night
8pm-5am		 Kanto - Route 14 Bird Keeper Josh
Teams

First Battle
Bird Keeper Josh Fearow
Level 37
Second Battle
Bird Keeper Josh Fearow Skarmory
Level 47 Level 44
Third Battle
Bird Keeper Josh Skarmory Fearow
Level 48 Level 51
Fourth Battle
Bird Keeper Josh Skarmory Fearow
Level 55 Level 55