Stream comes within Office 365/Microsoft 365 licencing. At the moment, Stream doesn't allow anonymous viewing of videos (it will do in the future) so at this time everybody needs to be a part of the organisation and licenced. This includes the Stream mobile app.
In terms of the users not already migrated to Office 365, it is possible. They would need an Office 365 licence, but just Stream enabled on it in the period prior to their migration. In other words, because you haven't migrated them yet, you could add Stream within the licence, have everything else off, then add the Stream mobile app or get them to use the web app (web.microsoftstream.com). Considering all this, you may just want to roll out Stream at the same time as exchange/office.
The decision is yours based on what is best for you and your users!