'Drawing' a random location on a grid... in secret

I was going to ask how big your board was and suggest a bag of numbered tiles from 1 to N (where N is the size of your board), but I realized that arguably, a more important question is: Is there an advantage to just letting the players pick where they start? If there is, that implies that there's a fair bit of "game position" luck in starting position. That's not a big deal for me, but it's important to recognize that as part of the game design.

If there's no advantage to letting players pick their "random" location, you can save a lot on components by just letting players pick. In this vein, you could have each player write three locations on a scrap of paper at the start of the game and toss 'em all in a hat. When you need a location, draw one from the hat, then write a new one down and toss it in the hat to replace the one you took. This would work well to simulate a semi-sentient intentionality to the game universe's selection of "random" locations.

Back to the numbered tiles: Say your board is 9x9. A bag of tiles with the numbers 1 through 9 repeated (say) 3 times is enough to give you 13 unique (X,Y) locations on the board – even more if you replace tiles during play. Intended use: Draw a tile. Put it behind your screen in your "X" slot. Draw another tile. Put it in your secret "Y" slot. That's the (X,Y) coordinate of your secret location. When you need a new location, toss your old tiles back in the hat and draw new ones.

By the way, is it important that no player's random location is the same as another player's random location? If so, that makes things a lot more complex.

Another "by the way": Your initial card deck idea works just fine if you replace every card drawn back into the deck and shuffle the deck after each replacement. All cards have an equal chance of being drawn on every draw. It's not that bad even if you just replace your card once you're done with it. (In fact, that's a great solution if you don't want players to have identical locations.)

Best of luck on your game!

Say your grid was like a Battleship board (10x10) that's numbered across the top and lettered down the side. You could just have one bag of letters and one bag of numbers and have each player draw a tile out of each bag.

If you wanted them to know something about where their opponents were, they could keep the tiles and then know if they drew E5, that no one else could be in the 5 column or the E row (since they have it still). Or if you had them put back the tiles so others could draw you would run into the problem of folks drawing very close positions or even possibly the exact same one.