Txtype 0 (non-EIP 1559) are not working

Start at safe_cli/safe_creator.py and trace the deployment call into gnosis/safe/proxy_factory.py, then inspect the web3 transaction-building failure shown in the logs. Reproduce the command against a non-EIP-1559 RPC such as Velas EVM and verify that Safe creation completes without requiring eth_maxPriorityFeePerGas or eth_feeHistory.

Describe the bug
Some EVM networks are without txtype 1 (EIP-1559) support.
It's not possible to use safe CLI with these networks due to error while sending tx to the RPC.
Logs attached.
Reproduced in all CLI versions starting from v0.8.0 to v1.4.0

To Reproduce
Steps to reproduce the behavior in Velas EVM (chain id 106):

safe-creator https://evmexplorer.velas.com/rpc [private key] --owners [...] --threshold ... --salt-nonce ... --safe-contract 0xfb1bffC9d739B8D520DaF37dF666da4C687191EA --proxy-factory 0xC22834581EbC8527d974F8a1c97E1bEA4EF910BC --callback-handler 0x017062a1dE2FE6b99BE3d9d37841FeD19F573804

Expected behavior
Safe created

Logs

Network VELAS_EVM_MAINNET - Sender 0x7f77094B1C2b982340E18E8D77578FDFA36e76cd - Balance: 5.000000Ξ
Creating new Safe with owners=['0x5503e1185c486c327b999b094b151474c1b9bb1f', '0xC57606E86bA5E6BFAa353E27CaE0251C8c2bf932', '0x7CE3ac7A7B4D1157A7004aBEAd8cD6e24f5C52F6'] threshold=2 salt-nonce=1736542422
Safe-master-copy=0xfb1bffC9d739B8D520DaF37dF666da4C687191EA version=1.3.0
Fallback-handler=0x017062a1dE2FE6b99BE3d9d37841FeD19F573804
Proxy factory=0xC22834581EbC8527d974F8a1c97E1bEA4EF910BC
Do you want to continue? [y/N]: y
Safe will be deployed on 0xA327cc41971f532c6be8EdB51692f5522B16Ae7a, looks good? [y/N]: y
/Users/anton/miniconda3/lib/python3.9/site-packages/web3/eth/eth.py:186: UserWarning: There was an issue with the method eth_maxPriorityFeePerGas. Calculating using eth_feeHistory.
  warnings.warn(
Traceback (most recent call last):
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/eth/eth.py", line 184, in max_priority_fee
    return self._max_priority_fee()
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/module.py", line 75, in caller
    result = w3.manager.request_blocking(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/manager.py", line 325, in request_blocking
    return self.formatted_response(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/manager.py", line 278, in formatted_response
    raise MethodUnavailable(error)
web3.exceptions.MethodUnavailable: {'code': -32601, 'message': 'Method not found'}

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/Users/anton/miniconda3/bin/safe-creator", line 8, in <module>
    sys.exit(main())
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/safe_cli/safe_creator.py", line 220, in main
    ethereum_tx_sent = proxy_factory.deploy_proxy_contract_with_nonce(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/gnosis/safe/proxy_factory.py", line 253, in deploy_proxy_contract_with_nonce
    return self._deploy_proxy_contract(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/gnosis/safe/proxy_factory.py", line 149, in _deploy_proxy_contract
    tx = deploy_fn.build_transaction(tx_params)
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/contract/contract.py", line 354, in build_transaction
    return build_transaction_for_function(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/contract/utils.py", line 232, in build_transaction_for_function
    prepared_transaction = fill_transaction_defaults(w3, prepared_transaction)
  File "cytoolz/functoolz.pyx", line 263, in cytoolz.functoolz.curry.__call__
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/_utils/transactions.py", line 132, in fill_transaction_defaults
    default_val = default_getter(w3, transaction)
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/_utils/transactions.py", line 75, in <lambda>
    lambda w3, tx: w3.eth.max_priority_fee
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/eth/eth.py", line 190, in max_priority_fee
    return fee_history_priority_fee(self)
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/_utils/fee_utils.py", line 46, in fee_history_priority_fee
    fee_history = eth.fee_history(*PRIORITY_FEE_HISTORY_PARAMS)  # type: ignore
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/eth/eth.py", line 228, in fee_history
    return self._fee_history(block_count, newest_block, reward_percentiles)
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/module.py", line 75, in caller
    result = w3.manager.request_blocking(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/manager.py", line 325, in request_blocking
    return self.formatted_response(
  File "/Users/anton/miniconda3/lib/python3.9/site-packages/web3/manager.py", line 278, in formatted_response
    raise MethodUnavailable(error)
web3.exceptions.MethodUnavailable: {'code': -32601, 'message': 'Method not found'}

If you need tokens for gas, feel free to post an address and I will send some.