A) 
I tested this on my centos 6.3 and it seems to work fine there:

=================================
sudo yum install Percona-Server-server-55
Loaded plugins: auto-update-debuginfo, fastestmirror, presto, security, upgrade-helper
Loading mirror speeds from cached hostfile
 * base: mirror.dhakacom.com
 * centosplus: mirror.dhakacom.com
 * contrib: mirror.dhakacom.com
 * elrepo: ftp.nluug.nl
 * elrepo-extras: ftp.nluug.nl
 * elrepo-kernel: ftp.nluug.nl
 * epel: mirrors.hustunique.com
 * epel-source: mirrors.hustunique.com
 * extras: mirror.dhakacom.com
 * fasttrack: mirror.dhakacom.com
 * updates: mirror.dhakacom.com
Setting up Install Process
Resolving Dependencies
--> Running transaction check
---> Package Percona-Server-server-55.x86_64 0:5.5.35-rel33.0.611.rhel6 will be installed
--> Processing Dependency: Percona-Server-client-55 for package: Percona-Server-server-55-5.5.35-rel33.0.611.rhel6.x86_64
--> Processing Dependency: Percona-Server-shared-55 for package: Percona-Server-server-55-5.5.35-rel33.0.611.rhel6.x86_64
--> Processing Dependency: libssl.so.10(libssl.so.10)(64bit) for package: Percona-Server-server-55-5.5.35-rel33.0.611.rhel6.x86_64
--> Processing Dependency: libcrypto.so.10(libcrypto.so.10)(64bit) for package: Percona-Server-server-55-5.5.35-rel33.0.611.rhel6.x86_64
--> Running transaction check
---> Package Percona-Server-client-55.x86_64 0:5.5.35-rel33.0.611.rhel6 will be installed
---> Package Percona-Server-shared-55.x86_64 0:5.5.35-rel33.0.611.rhel6 will be installed
---> Package openssl.x86_64 0:1.0.0-25.el6_3.1 will be updated
---> Package openssl.x86_64 0:1.0.1e-16.el6_5.4 will be an update
--> Finished Dependency Resolution

Dependencies Resolved

=====================================================================================================================================================================================================================
 Package                                                     Arch                                      Version                                                      Repository                                  Size
=====================================================================================================================================================================================================================
Installing:
 Percona-Server-server-55                                    x86_64                                    5.5.35-rel33.0.611.rhel6                                     percona                                     15 M
Installing for dependencies:
 Percona-Server-client-55                                    x86_64                                    5.5.35-rel33.0.611.rhel6                                     percona                                    6.2 M
 Percona-Server-shared-55                                    x86_64                                    5.5.35-rel33.0.611.rhel6                                     percona                                    644 k
Updating for dependencies:
 openssl                                                     x86_64                                    1.0.1e-16.el6_5.4                                            updates                                    1.5 M

Transaction Summary
=====================================================================================================================================================================================================================
Install       3 Package(s)
Upgrade       1 Package(s)

Total download size: 24 M
Is this ok [y/N]: n
Exiting on user Command
raghu archie:~ [116:1]% rpm -qa | grep -i percona
percona-release-0.0-1.x86_64

========================================================================

B) 

"These versions of the libraries were not introduced until RHEL 
6.5, therefore installation / upgrades fail on any older point 
release." 

This is incorrect. The openssl update is available for CentOS 6.3 
as well (as is with centos).

 rpm -q openssl
openssl-1.0.1e-16.el6_5.4.x86_64

rpm -ql openssl | grep libcrypto.so
/usr/lib64/.libcrypto.so.1.0.1e.hmac
/usr/lib64/.libcrypto.so.10.hmac
/usr/lib64/libcrypto.so.1.0.1e
/usr/lib64/libcrypto.so.10

C) I see last few comments have tried installation with rpm and 
it has failed. You need to use yum to resolve non-local 
dependencies. So please test with that.

D) Now, in original description, it didn't seem to install the 
package - that may be due to other factors including broken 
yum-db or 'CentOS updates' repo not enabled (which is enabled in #1).