I'm not aware of any requirement placed on the Archive:: namespace for all modules there to have a similar API or to only work on certain archives. At the moment it feels to me like the most natural place for such a module.
No, I don't see any issues with using constructor names different from new, in fact this might make the code more readable later on. Just make sure to pick names that really do describe what the constructor is doing, and don't overload it too much - feel free to add more than one constructor with different names if that fits better.
I would say key/value pairs (hash), as in $record->replay( foo => "bar" ) - that is IMO one of the most flexible ways of doing it.
If you mean that $object->method as well as $object->[...] and $object->{...} should work, then yes, overloaded array/hash dereferencing that returns a tied array/hash does work (Update: I've done this myself before, but my classes for the two tie classes are different from the object's class!). Just keep in mind that you wouldn't be able to use that API for anything else then.
Before you overload an operator, I'd suggest providing a method to do the operation. An overloaded operator can always be added later. (Similarly for the above point.)
I'm not sure, but I would suggest providing both a low-level API that doesn't try to do anything fancy, so users can choose to use that for precise control of what happens, and optionally a higher-level API that tries to do the "right" thing (what that means will also be a question of experience with the module).
I would say "why not?", but not meant rhetorically - I probably don't know all the issues involved with doing this?
I don't know enough about WARC to give a good answer here...