The game stores trainer teams for every battle; this is an entirely separate chunk of code compared to what starters you may choose from. You'd have to edit the trainers for the rival.
The game stores game text, you'd have to modify that too.
Unfortunately, there are no all-in-one easy-to-use tools or guides for NDS games.