Not only that, but 00
isn't "a null" by any stretch of the imagination -- it's a 2-characters string. You appear to silently assume that your string is made up of substrings each of two hex digits, and any string operation you perform will have no idea about this little private convention of yours -- if you do manage to "replace a random 00" it might well be one made up of the second digit of, say, "F0", followed by the first digit of, say, "03": not what you probably mean!
A logically cleaner approach is to first split your string into the 2-digits pieces, thus making your unspoken assumption clear and explicit instead:
>>> string = "4100360036000000570046004200410061006200730020003600"
>>> pieces = [string[i:i+2] for i in range(0, len(string), 2)]
>>> pieces
['41', '00', '36', '00', '36', '00', '00', '00', '57', '00', '46', '00', '42', '00', '41', '00', '61', '00', '62', '00', '73', '00', '20', '00', '36', '00']
>>>
Yes, this can be made much more concise, but I'm striving for clarity and conceptual sharpness here!-).
Now locate all the '00' digits:
>>> where0s = [i for i in range(len(pieces)) if pieces[i] == '00']
>>> where0s
[1, 3, 5, 6, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
(again, easy to make compact, but this is the clearest way;-).
Now get a random choice out of the where0s and either remove it, or replace it with, for example, 'BA', then rejoin the string:
>>> import random
>>> pickone = random.choice(where0s)
>>> pickone
25
>>> # if replacing:
...
>>> pieces[pickone] = 'BA'
>>> ''.join(pieces)
'41003600360000005700460042004100610062007300200036BA'
>>> # if removing:
...
>>> del pieces[pickone]
>>> ''.join(pieces)
'41003600360000005700460042004100610062007300200036'
>>>
If this is indeed the exact operation you want to perform, but you want more conciseness and speed rather than this totally-spelled-out clarity, we can of course keep developing the idea!