Although I was baptised as a Christian, I feel a strong sense of connection to Judaism and would like to use the Mikvah. I understand that some people believe there is no point/need because I am not Jewish (nor married) and therefore it has no meaning, however, I would still really like to visit one one day. I feel like I need to fill this spiritual void within myself. Is this permissible?
The most accessible form of mikva is a natural lake or the ocean (assuming you live near a coast). These are considered the ideal mikvaos though most use man-made mikvaos for a variety of other reasons. Natural springs also qualify as mikvaos and in fact purify from things which conventional mikvaos do not. All of these are easily accessible to anyone.
I cannot answer this question for all non-Jews but as a Jew by choice who had an Orthodox conversion almost 30 years ago I can say that I was denied the use of one mikvah (after presenting my conversion papers) and encouraged to have (another) Orthodox conversion before requesting to be able to use another one. So I'm going to say that it depends on the people running the particular mikvah but it is probably not allowed.
No you should not be visiting the mikvah. Mikvahs are specifically built for the Jewish community (exception being those who wish to join via conversion are required as part of that process). Whilee the idea of mikvah be seem nice it is important that G-d has a designed path for each of us to follow. I would suggest you take a look at this website which talks about the 7 laws given to Noah and his descendants... http://www.noahidenations.com/ also this article... http://www.chabad.org/kabbalah/article_cdo/aid/380332/jewish/The-Mitzvot-of-Non-Jews.htm