Logo in footer with aligned text

Here's another possibility, using this time the background package; using this package you can place the structure at any desired location on the pages of your documents:

\documentclass{article}
\usepackage{graphicx}
\usepackage{url}
\usepackage{background}
\usepackage{lastpage}
\usepackage{lipsum}% just to generate text for the example

\backgroundsetup{
  scale=1,
  color=black,
  opacity=1,
  angle=0,
  position=current page.south,
  vshift=60pt,
  contents={%
  \small\sffamily%
  \begin{minipage}{.8\textwidth}
  \parbox[b]{.6\textwidth}{%
    Page \thepage\ of   \pageref{LastPage}}\hfill
  \parbox[b]{.4\textwidth}{%
    \raggedleft My Company, My street 1 \\ 1234 city, Country}\\
  \textcolor{red}{\rule{\textwidth}{1.5pt}}\\
  \url{www.mycompany.com}
  \end{minipage}\hspace{.02\textwidth}%
  \begin{minipage}{.18\textwidth}
  \includegraphics[width=\linewidth,height=70pt,keepaspectratio]{ctanlion}
  \end{minipage}%
  }
}

\pagestyle{empty}

\begin{document}

\lipsum[1-40]

\end{document}

Am image of the first two pages:

And a zoom to the bottom of one of the pages:

CTAN lion draw­ing by Duane Bibby; thanks to www.ctan.org

Here is my take at it. It is not well defined but sort of does what you are looking for.

\documentclass[letterpaper]{article}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{calc}
\footskip=70pt
\def\companylogo{\rule{2cm}{2cm}}
\fancypagestyle{companypagestyle}
{
    \fancyhf{}
    \fancyfoot[L]
    {
        \parbox[b]{\dimexpr\linewidth-2.5cm\relax}
        {
            \sffamily \bfseries\hfill MyCompany, MyStreet 1\\
            Page \thepage\ of \pageref{LastPage}\hfill 1234 City, Country\\
            {\color{red}\rule{\dimexpr\linewidth\relax}{0.4pt}}\\
            www.mycompany.com
        }
    }
    \fancyfoot[R]
    {
        \parbox[b]{2cm}{\companylogo}%
    }
}

\pagestyle{companypagestyle}
\usepackage{lipsum}
\begin{document}
\lipsum
\end{document}