1. I think they Could Make Rewind work, but they would have to put like a Meter on it or something so people don't spam it. Rewind would probably Have you refresh at the Postion you were second ago, Revert the Damage done to you, and perhaps if you lost a stock you can even Regain it.
2. Steve was Actually kinda Expected from the Early days of FP1 Speculation. Once Banjo got in he kinda fell off, until well, he actually got in. It's the same Deal with Byleth where Byleth was expected as DLC until it seemed FP1 was 3rd party Only, but then Byleth got in anyway
Honestly, I think the only character kinda guessed at for DLC without leaks was Banjo, and Only some were predicting that. Between the War between Banjo and Steve and people thinking Banjo was Impossible, it wasn't widespread
Every other chaacter predicted either had Leaks like with Hero and Terry, Got in when they were not in Speculation Like Byleth, ARMS, and Steve, or were just not Predicted at all like Joker
That's the thing though - whenever Rewind's a thing in a game, there is a (or a couple) limit(s) to it.
In Overwatch, Tracer's Recall has a 12 sec cooldown (I've mentioned Dota 2's Weaver in the past - his Time Lapse works in a similar fashion and has a mana cost early game.). Likewise, Tracer's Blink has 3 seconds CD per charge, and she has 3 charges in Overwatch.
It's different from Sands of Times' Prince of Persia, who has limited uses of the Rewind and can only refill it by killing enemies and taking their Sand. Any way, there is a lot of constraints on Rewinds, and those limitations would translate to Smash in some form by neccesity.
NGL, even with that meter that still sounds broken, especially if you can regain stocks. I'd rather have Tracer be playable without that ability.
None of these allow stocks to come back - deaths are not erased by Recall, death timers scale with levels in Dota 2 (unless one uses the very risky buy-back, which itself has a long cooldown and generally high cost when used; and the next death after buyback increases the death timer even further, to hideous levels late game) and Sands of Time punishes deaths by sending the Prince back to the last checkpoint. Again. no deaths are erased by rewinding in any of these games - and that would likely translate to Smash.
IIRC Tracer's Recall doesn't go back to a position before death. Recall has the potential to restore health, but up to where it was 3 secs prior. The 12 secs CD is a lot of time in Smash too - in that time she can wind up taking lots of damage or even be KOed, even without the threat of headshots oneshotting her.
Tinkering with the limitations and adjusting them for Smash might be a way to go. Extending the CD a bit for example, although Tracer's characterized as a lightweight (she'd be lighter than ZSS perhaps) so she could be balanced that way too.