Am I stuck with installing native software wallets for each coin? What about paper wallets?
Some coins (Dogecoin) have paper wallet.
Some coins (Monero, Waves) have deterministic seed.
And for some other coins you don't have other choice than keeping somewhere safe the wallet.dat (or equivalent) file.
But each and every coin has its own community. Go and ask for each coin you are interested in, since there's no universal solution.