The main challenge in what you're describing seems to me to rely on rules resolution. There are many ways to resolve rules and the tools you're omitting are probably the ones we're most familiar with. Anything not familiar may still be viable but likely cumbersome.

Here's an example similar to Star Control's melee mode: It's a ship to ship battle game where fleets engage each other one ship at a time. At the start of the game players buy ship hulls and modules, both of which sit in a visible pool before them. There's no game board and the theme is hard science fiction, which basically means that ships don't engage like World War II battleships but rather at high velocities and vast ranges with battles resolved in minutes.

The game lasts for a number of turns equal to the number of ships. At the start of a turn both players choose their hull and place it before them, then place modules. Modules come in a variety of flavors (defensive, offensive, vital, special) but must match in slots, which are laid out on the ship sheet in a puzzle-like fashion. Modules can also be placed outside the ship, representing things like hunter-killer drones, diamond particle clouds and reflective armor arrays (these are placed off the ship sheet and represent free floating objects moving along with the ship). Internally adjacent modules can affect and protect one another, allow modules to switch position, offer redundancy.

At any time each player can see the ship the other player is throwing into battle. However, to make it interesting players only have 10-30 seconds, depending on difficulty level, to assemble each ship.

Once assembled, modules are eliminated in a rock, scissors, paper fashion from outermost to innermost as players take turns choosing which module to activate and which module to target. Some modules, like weapons, have limited ammo markers (board pieces themselves). Some modules have multiple effects when damaged (represented by turning the module counter on the ship sheet), even cascading effects to neighbors or along conduits visible on the ship sheet. Damage is alternately determined by attacker then defender. Ships can only make one action a round, either turning to rotate modules into position, rearranging a module, defending or attacking (depending on whose turn it is) or using a module to repair another module.

When a ship loses all vital modules or all modules in total, it is destroyed and the hull sheet, along with modules, is removed. The game ends with the winner being the player with ship hulls remaining, or draw if all hulls are destroyed.

You could add rules on top of this, such as allowing players to change tactics each turn, which might change functioning of modules (unless this constitutes as hidden information). Even without a board you could denote the idea of relative spatial positioning, breaking the engagement into long, medium and close range, changing the effect of modules or only allowing some to function at different phases.

One trade-off would be whether you risk watching your opponent build their ship or pour all your time into getting as much onto your ship sheet as possible. If actions against modules had multiple outcomes, chosen alternately by attacker and defender, there would be more variety as well.

I've never tested this so I've no idea if it would be a good game but it seems to me that limited time can act as a stand in for things like dice rolls and hidden information.

I recommend interaction between players as a way to introduce uncertainty without random elements. Simultaneous turns are the most obvious choice, but every time outcomes depend on what opponents do there is an element of prediction of others' moves.

For example, imagine playing Dominion without randomness, by stacking the deck each time it would be shuffled: you cannot simply plan a (very long and complex) sequence of optimal turns, you must adjust to what each opponent is expected to do many turns before they do it.

Once I had a friend who had just sold his massive Magic The Gathering card collection, and he saw my cards and was sad that he couldn't play, so I proposed that we play with note cards, and he pointed out that it would be ridiculously easy to mark the cards and take too long to make decks. After some discussion what we ended up doing was creating the rule that on your turn you could draw 1 land and 1 other card, and play both, and they could be anything you wanted from all existing MTG sets. You could not use the same card more times than tournament legal though. It made for a few very interesting games as we were figuring out which cards were most effective this way. It did involve hidden information a little though because you could choose a counterspell and keep it hidden in your hand until you wanted to use it.