if you choose the C major key, and start a chord progression with a chord other than the tonic chord, OR the tonic chord does not even appear in the progression, how do you know that you are still in a C major key?
I know it, because I feel it. If I don't feel it, it's not there. If I'm not sure of my feelings, I can test them by playing a candidate tonic chord to see how it makes me feel.
I feel the pull or harmonic "gravity" towards a center, if the song's notes, chords and rhythmic structures are arranged so that it creates that pull. There are phrases and movements that feel like they would come to a natural conclusion by playing the imagined tonic chord. The tonic chord doesn't need to be actually heard at any point in order to create that pull. Sometimes songs give the tonic away too easily and too often, making the song feel boring or cheap. (Excluding modal techno etc where the whole point of the style is to keep banging on the tonic and not have any "changes" to begin with, and sense of movement and journey is created through other means.)
To study the tonic phenomenon, you can take an existing tune that gives the tonic chord at one or more points, and replace all such instances with a different chord. Or you could simply cut out those segments from the piece entirely or replace them with silence or noise or unpitched rhythm. If the piece is strongly harmonically crafted around the tonic, removing the tonic chords should not cancel the sense of harmonic center, it should just keep the listener in suspension, waiting for the tonic chord that never comes. But it doesn't change the key of that song - IF the song is harmonically properly made to give the impression of that chord being home.
I'm sure there are songs that don't very strongly point to a tonic and where removing the tonic chords would destroy the balance. In such tunes I wouldn't feel enough harmonic pull without the tonic being actually played, or the sense of center might be positioned somewhere else.
It is also possible to make harmonically ambivalent or chaotic music - we could call it atonal - that does not give a listener the impression of homing in on any particular note or chord. For example by selecting notes and their rhythmic weights randomly.
Using any specific set of pitches by itself does not place the notes in a key. This is sometimes demonstrated by beginning musicians who ask, how come the different modes of, say, C major, can be different modes since they have all the same notes. What makes D Dorian and F Lydian different because all the notes are the same... Do you announce to your listeners before starting to play that they are adviced to hear F as the tonic of your random note salad, and then it is in F Lydian? No, you have to draw a consistent musical image with your notes.