If you need tiles, the loose tiles database here on the site has a wide collection, and you can search tags such as whether it's classic, gameboy, or etc. There aren't many classic spriters around, but classic's quality means that you can probably do a low effort spriting attempt and most people won't bat an eye.
I highly recommend you don't edit 1st.qst if you want to make a Z1 remake and have new tiles, as the tileset used for 1st.qst is very outdated and doesn't have a lot in it. Instead, try using this: TLoZ 2.5 Classic + Koten 1.3 - Quests | PureZC
That's a remake of the 1st and 2nd quests done in either the new 2.50 classic tileset, or the koten tileset (your choice). There may be a few inconsistencies (such as the dropset), but you'll find the organization better overall.
ZC is limited to 256 colors; you cannot "add" csets. Generally speaking, if you want global colors, you want to edit CSets 7, 8, 10, and 11; 0, 1, and 5 can also be edited but keep in mind the subscreen uses these colors so make sure you edit the subscreen accordingly. ZC has level palettes which swap out Csets 2, 3, 4, and 9 (as well as 1, 5, 7, and 8 in the newer dev builds); 9 is intended to be used for enemies who are limited in where they appear and need special colors, or enemies which change their color depending on the level. You might be able to get away with some sleight of hand with this knowledge to "fake" having more colors, but if you look at stuff like mine and FireSeraphim's Hyrule Fantasy project (a Z1 remake made in a much more pretty tileset), we managed to get some really nice looking enemies with only the colors in CSets 7 and 8, so I have faith you can do it too if you manage your colors well.
If I were to guess why your changes were lost; were you writing over Csets 2, 3, 4, 6, or 9? Those Csets get overwritten by level palettes or, in the case of cset 6, link's palette. I hope it's something like that and not a possible new bug.
