After some thought, I believe that neither Fact 1 nor the Claim are actually true as stated. Fact 2 is true, but does not imply Fact 1. The argument against Fact 1 is simple: let $X = S^1 = \{z \in \mathbb{C} \mid \lvert z \rvert = 1\}$ be the circle, let $p \colon [0,1] \to S^1$ be $p(t) = e^{2\pi i t}$, and let $c \colon [0,1] \to \{x_0\} = (1,0)$. Then $p$ is very much homotopic to $c$, say via
$$H(s,t) = e^{2\pi i st};$$
we have $H(s,0) = c(s)$ and $H(s,1) = p(s)$. But $p$ is not homotopic to $c$ through loops, as Fact 1 claims. This is tricky to prove (how do you show that some homotopy doesn't exist?) and one would normally prove it with covering spaces, which show immediately that anything homotopic to $p$ has winding number $1$, while $c$ clearly has winding number $0$. I will simply leave it at that, since I don't think you can really do this with your current level of technology.
Note that any path is homotopic to any point along it, by a similar trick: just pick any $t_0 \in [0,1]$ and, since the interval is contractible, choose a continuous contraction $f(s,t)$ from the identity to $t_0$; for example,
$$f(s,t) = t_0 + s(t - t_0)$$
(at $s = 0$ you get $t_0$, at $s = 1$ you get $t$, and since $0 \leq s \leq 1$, we have $f(s,t) \in [0,1]$; in fact, $f(s,t)$ is between $t$ and $t_0$ for all $s$). Then given a path $p \colon [0,1] \to X$, the map $F(s,t) = p(f(s,t))$ is a homotopy from $p$ to $p(t_0)$. As the other answer says, homotopy of paths without fixing endpoints is pretty meaningless.
Anyway, the Claim is an even more specific fact, that $p$ and $c$ must be homotopic through loops based at $x_0$. This is impossible for the same reason.
I am actually a bit puzzled where you got Fact 1 from. I have a copy of the book Algebraic Topology by Greenberg and Harper, presumably a revision, and the proof in question is covered entirely, and without unproven claims, by just Fact 2 (their Lemma 3.3). I believe you may have misinterpreted the key step in the following expanded version of the argument there, which does produce a homotopy with the properties given in Fact 1, but from stronger hypotheses.
Theorem: If $X$ is contractible, then it is simply connected.
Proof: Let $p \colon [0,1] \to X$ be any loop with $p(0) = p(1) = x_0$. Because of this, we can define a new continuous function
$$q \colon S^1 \to X$$
where we consider $S^1 = [0,1]/(0 = 1)$. More explicitly, let $f \colon [0,1] \to S^1$ be the continuous map identifying $0$ with $1$, so we have $p = q \circ f$.
Suppose $X$ is contractible; then there is a homotopy
$$H(x,t) \colon X \times [0,1] \to X$$
with $H(x,0) = x$ and $H(x,1) = x_0$ from the identity function to the constant function $x_0$. From this, we define a map
$$H' \colon S^1 \times [0,1] \to X$$
by $H'(s,t) = H(q(s),t)$. This is a homotopy from $q$ to $x_0$, since
$$\begin{align}
H'(s,0) = H(q(s),0) = q(s) &&
H'(s,1) = H(q(s),1) = x_0
\end{align}$$
It is continuous, being a composition of continuous functions. Define a further homotopy
$$F(s,t) \colon [0,1]^2 \to X$$
by $F(s,t) = H'(f(s),t)$. It is continuous and a homotopy from $p$ to $x_0$, since
$$\begin{align}
F(s,0) = H'(f(s),0) = q(f(s)) = p(s) &&
F(s,1) = H'(f(s),1) = x_0.
\end{align}$$
$F$ has the property that
$$\begin{align}
F(0,t) &= H'(f(0),t) = H(q(f(0)),t) = H(p(0),t) = H(x_0,t) \\
&= H(p(1),t) = H(q(f(1)),t) = H'(f(1),t) = F(1,t).
\end{align}$$
That is, $F$ satisfies the criteria of Fact 1. (Note that we had to use the global homotopy $H$ to get $F$, not merely a homotopy from $p$ to $x_0$.) Defining $\alpha = \beta$ to be this common vertical-edge path, which is actually a loop at $x_0$ since $F(0,0) = F(0,1) = F(1,0) = F(1,1) = x_0$, we get from Fact 2 that $\alpha^{-1} p \alpha$ is homotopic to $x_0$ as loops based at $x_0$. That is, we have
$$[\alpha]^{-1} [p] [\alpha] = [x_0] = 1$$
as homotopy classes in $\pi_1(X, x_0)$. Moving $[\alpha]$ to the other side, we get $[p] = [\alpha][\alpha]^{-1} = 1$, so $[p]$ is the trivial element of the fundamental group. Since $p$ is arbitrary, $X$ is simply connected. $\square$
Based on the manipulations in this proof, the best approximation to Fact 1 that I can come up with is:
Proposition: Let $X$ be a topological space and $f, g \colon X \to X$ two homotopic continuous maps. Then for any loop $p \colon [0,1] \to X$ based at $x_0 = p(0) = p(1)$, there is a homotopy $F \colon [0,1]^2 \to X$ from $f\circ p$ to $g\circ p$, both loops at $x_0$, such that for each $t \in [0,1]$, the path $s \mapsto F(s,t)$ is a loop based at $x_0$; i.e. $F(0,t) = F(1,t)$ for all $t$.
Proof: In short, make $p$ into a map $q$ from the circle and compose the assumed homotopy from $f$ to $g$ with $q$ in the first variable. Then, unwrapping the circle, you find that the resulting homotopy from $f \circ p$ to $g \circ p$ has the property claimed. The details are above. $\square$
Best Answer
Your idea is correct, but the moving $p$ is detail to be taken care of. I like to fix bad homotopies by messing with the square, since the space is too complicated. Imagine starting at the bottom-right corner of the square. Then going backwards along the bottom is going along the path $\sigma(t)$ of the point $p$. That is, $\sigma(t) = h(t,p)$. If we then go up, this goes along our path $\gamma$, and finally we go along the top, tracing $\sigma$, in the forward direction. So your square seems to be a "weird homotopy" from $\sigma^{-1} \ast \gamma \ast \sigma$ to the constant path, with the former path along three of the sides instead of just one. However, I claim that a clever transformation $I^2 \rightarrow I^2$ can turn this "weird homotopy" you defined into an honest homotopy from $\sigma^{-1} \ast \gamma \ast \sigma$ to the constant path.
EDIT: You must, of course, then figure out how to move from this to the fact that $\gamma$ is homotopic to the constant path. For this, you will either apply a nice theorem or attempt another fudge map for your square.