Just to add some numbers: I simulated your circuit with the values given in your circuit and some sensible defaults (e.g. Vcc=9V and Vin=1V peak-to-peak).
Results are, that you operate the transistor very close to the maximum ratings.
I see a peak power dissipation of 627mW and an average power dissipation around 450mW. The maximum rating for the 2N3904 is 625mW, so no surprise that the transistor gets hot fast.
If you drop a TIP41C into the circuit you should still be able to measure a signal at the amplifier output, but it will probably a lot lower because the current gain of the TIP41C is a magnitude lower compared to the 2N3904.
As others already suggested you can run the TIP41 and the 2N3904 in darlington configuration. That'll will give you best of both worlds.
Nonetheless, from the learning experience I think your circuit is quite a success. It's running hard at the limit of the 2N3904 but otherwise it looks fine. I suggest that you take a look at differential amplifiers next. They are a very important building blocks for audio amplifiers.