The tiefling has Fire Resistance and Hellish rebuke, which both have to do with fire damage. If I were to replace that with Cold damage, Slashing damage, Necrotic damage, Radiant damage, Psychic damage or any other damage type (assuming it made sense narratively), would it break or mess up the balance of the game in any significant way?
It depends on your campaign
The strength of any kind of damage depends on the campaign. While Sparksbet mentions the resistances from Monster Manual in this question - it matters a lot less than it seems. You are not using every monster in the Monster Manual. You are not even randomly picking monsters from the monster manual using an uniform distribution (I mean, you could be, but those would be two amazingly awkward, but possibly funny, campaigns). So, ultimately, it depends on your campaign.
If your campaign contains many monsters that are weak to fire, then yeah, changing it to anything else makes the Hellish Rebuke weaker. If you are in a campaign where the party is fighting red dragons and fire elementals, yeah, you would be doing a favor to the PC changing the damage type.
While András answer there does an amazing job, you are also (probably) not playing from 1 to 20. Again, what type of damage is most resisted/immuned also depends on the level range, which is also part of the campaign. For example, in Tier 1 (levels 1-4), monsters with immunity to physical (Slashing/Piercing and Bludgeoning) nonmagical damage are rarer, because otherwise martial fighters (Fighters, Barbarians, etc.) would suck too much without having magic weapons - which they don't early. On the other hand, in later levels, almost every monster has immunity to nonmagical physical damage.
So, while my answer might seem unhelpful, that's all we can correctly provide without more information about the actual campaign.
Finally, I will agree with Sparksbet conclusion: Ultimately, honestly, this change is not what is going to make Tieflings unbalanced (for better or worse). Giving them wings will :P (this is a joke, don't punch me please).
Note on Physical Damages
Giving resistance to physical damage is usually a no-no. You mentioned "Slashing" as a possibility - resistance to slashing would be way stronger than magical resistances. Evey creature has some attack that deals physical damage - even the highest CRs - and resistance to even magical slashing (or piercing, or bludgeoning) damage would be way stronger than anything else. Quoting the DMG in the Creating a Monster section, as an example of how "especial" these damage types are.
Giving a monster resistances and immunities to three or more damage types (especially bludgeoning, piercing, and slashing damage) is like giving it extra hit points.
This depends on which type of damage you change it to.
When it comes to Hellish Rebuke, different monsters are resistant or immune to different types of damage, and some types are more often resisted than others, which could make your altered versions of the spell more or less useful. According to this answer, which accounts for the monsters in the 5e Monster Manual, fire is one of the more common types of resistances and immunities. Changing to poison damage, which is by far the type with the most immune monsters, would likely weaken this ability. Changing to cold damage, which has more resistant monsters but fewer immune monsters, or lightning damage, which has a bit fewer of both than fire, wouldn't likely affect it enough to be noticeable. Acid, necrotic, or thunder have much fewer resistant or immune monsters, so they may affect things more; force, psychic, and radiant have hardly any creatures that are resistant or immune to them. This could definitely lead to the spell being more powerful against more monsters.
As for resistance, I do not have data on which damage types are most frequently dealt by monsters (I'd welcome it if someone else has it!) but I'd wager it's a similar situation -- some damage types would be more common and thus more likely to affect the course of the game.
That said, I don't think any change in damage type for these would make tieflings unbalanced compared to the other PC races. Frankly, it doesn't even make you as OP as some other tiefling variants. So I wouldn't personally worry too much about allowing this change.