Do I have to know RSA padding scheme in advance when verifying signature with EVP_Verify*? Is there a way to figure out what RSA padding type was used on signature during verification (when calling EVP_VerifyInit, EVP_VerifyUpdate and EVP_VerifyFinal) or is it a matter of convention which has to be known in advance?
For this answer I'll be focussing on solely on RSA (the RSA tag is present, so I'll suppose that this question is just about RSA). It is also the most likely signature scheme that requires padding, I suppose.

TL;DR: you don't just need to know the padding scheme in advance, but also the other configuration options to be used, such as data hash method and MGF1 (configured with it's own hash), salt and label for PSS.



Yes, the padding scheme is something that needs to be known in advance during verification and of course signature generation. There is no easy way of verifying which padding scheme is used from within most signature schemes without first performing modular exponentiation yourself, after all.

If you'd allow both PKCS#1 v1.5 padding for signature generation and PSS during verification (and rely on the verification result to be true for either one of them) then your verification may fail if a successful attack is launched on either one of the two schemes. Besides that, it would require you to perform the signature generation twice.

The same goes for hash functions, where the acceptance of a hash from a weaker hash function may lead to insecurities. Even if these kind of insecurities are not directly visible or possible, in general the security proofs of the algorithms generally do now allow the key to be used for different schemes.

Sometimes there are indications that using keys for different schemes is problematic. E.g. for PSS the following can be found in PKCS#1 v2.2:


  This encoding method is parameterized by the choice of hash function,
     mask generation function, and salt length. These options should be
     fixed for a given RSA key, except that the salt length can be
     variable (see [JONSSON] for discussion).




Similarly, the withdrawn ISO 9796 specifications for signatures giving message recovery make it explicit that the configuration options need to be known in advance. It contains a section with three options in that respect:


  Use of the signature schemes specified in this standard requires the selection of a collision-resistant hash-function h. There shall be a binding between the signature mechanism and the hash-function in use. Without such a binding, an adversary might claim the use of a weak hash-function (and not the actual one) and therebyforge a signature.NOTE 1There are various ways to accomplish this binding. The following options are listed in order of increasing risk.
  
  
  Require a particular hash-function when using a particular signature mechanism. The verification process shallexclusively use that particular hash-function. ISO/IEC 14888-3 gives an example of this option where the DSAmechanism requires the use of Dedicated Hash-function 3 from ISO/IEC 10118-3 (otherwise known as SHA-1).
  Allow a set of hash-functions and explicitly indicate the hash-function in use in the certificate domain parameters.Inside the certificate domain, the verification process shall exclusively use the hash-function indicated in the certificate.Outside the certificate domain, there is a risk arising from certification authorities (CAs) that may not adhere to theuserís policy. If, for example, an external CA creates a certificate permitting other hash-functions, then signatureforgery problems may arise. In such a case a misled verifier may be in dispute with the CA that produced the othercertificate.
  Allow a set of hash-functions and indicate the hash-function in use by some other method, e.g., an indication in themessage or a bilateral agreement. The verification process shall exclusively use the hash-function indicated by theother method. However, there is a risk that an adversary may forge a signature using another hash-function.
  


I've included this mainly to show that when it comes to calling signature verification methods that the configuration options of the signature functions need to be known in advance. It makes sense that the signature algorithm itself and padding method should then also be known in advance.



For debugging or reverse engineering the methods used, it makes sense to perform modular exponentiation first. For PKCS#1 v1.5 padding the padding bytes will be immediately identifiable. If it just looks like random data then you are most likely dealing with a PSS signature scheme. Generally you can distinguish various initial and trailing bytes of the padding method as well. Unfortunately many different padding methods have been used in the past, more than you might imagine.