A workaround is to provide more gas than might be needed, for example 10-50% more gas, because unused gas will be refunded.
It's also important to design contracts so that their gas usage is bounded. When using arrays and iterating, it's important that if the array keeps growing without limit, that you only iterate over a fixed number of items per transaction. A function's interface could look like
iterate(startingIndex, numberOfItems) and each transaction would pass the next
Solidity docs on Gas Limit and Loops:
Loops that do not have a fixed number of iterations, for example,
loops that depend on storage values, have to be used carefully: Due to
the block gas limit, transactions can only consume a certain amount of
gas. Either explicitly or just due to normal operation, the number of
iterations in a loop can grow beyond the block gas limit which can
cause the complete contract to be stalled at a certain point.
Do not iterate over the whole array in a single loop, because it could exceed the block gas limit, and permanently block the remaining part of the contract from executing. For a real world example see How to clear large arrays without blowing the gas limit?